next »

[BorisTheBrave]

Guys, I said I had N=n*2^n cells.

Basically, I was thinking of drawing a binary tree of depth n. You can arrange that all the 2^n leaves of the tree are equidistant from the root pretty easily, so they'll all be in the open set at the same time. And clearly, the tree can be drawn inside a rectangular grid of size 10n by 10*2^n.

I thought it was worth mentioning, because I had the same naive guess as lithander that the open list was bounded by 2*Sqrt(N). But in this case, sqrt(N) = sqrt(n * 2^n) = sqrt(n) * 2^(n/2) which will be smaller than 2^n for large n. So it's a counter example to the sqrt thing. Of course, it's not a square grid - but the original question never stipulated that. Though I'm pretty sure i could do the same trick in a square with a bit more effort.

To put some concrete numbers, if n=20, then the tree would fit in a grid of 200 by 2,000,000, meaning it required max 400,000,000 cells. But it would need an open set of over a million, which is a lot more than sqrt(400,000,000) = 20,000.

[BorisTheBrave]

Yeah, in fact this is a much better example:

http://www.shapeways.com/product/4R3DD2USJ/h-tree-space-filling-fractal-tree-in-2d

It's pretty square, and just from staring at it you can see the required open set (i.e. the tips), is a very high proportion of the total area (though, I'm not quite sure asymptotically if it's actually a constant proportion).

[gimymblert]

N=d*2^d cells

[Dacke]

Yeah, I got confused by N and n, with lithander talking in terms of N.

If you can construct the graph arbitrarily, you can just make a star graph. Start by expanding the central node and you'll get N-1 expanded ones next.

With A* you could construct an heuristic to exactly manipulate the order in which nodes are explored. So reasoning about fractals makes sense there.

But with Dijkstra’s, how do you get a fractalish shape with lots of open nodes?

[BorisTheBrave]

I don't think I can explain it better than picture:


Isn't it clear that every end point is equidistant from the center, and that it could be drawn on a standard grid?

[ThemsAllTook]

I'm running into problems with the stack when trying to create a floodfill function on my tilegrid.
[...]
Now weird thing is, I had a debug function "setTile( tileX, tileY, 1 )" which sets some uv coords for a tile. When this line is included, it doesn't cause a stack-overflow somehow. Is this somehow releasing the stack? FloodFillTile() is the function I'm calling btw.

The stack is a mysterious thing, and behavior like this is likely to change depending on platform and OS version. A safer way to do flood fill is to use a for loop and backtracking instead of recursion. The way I've implemented it in the past is that each iteration of the loop checks the four surrounding cells in some fixed order, moves to the first unfilled one of the same color, and pushes some information describing the direction it moved into a list. When a dead end is reached, pop the last thing off the backtrack buffer, and continue the process from there if it has any more fillable cells next to it. When you've backtracked to your starting position and there are no more fillable cells next to it, the flood fill is complete.

[Dacke]

@ Boris
Apparently I'm terrible at reading today

I think the endpoint/cellcount ratio asymptotically approaches 1/12 for the h-tree. But I'm pretty stupid today, so I'm not sure.

[BorisTheBrave]

Now I think about it, I agree, 1/12.

[ProgramGamer]

Game Maker: Studio question here:
I tried to make a script which word wraps a string of text passed as an argument. I then have a text box object which displays it on screen. Problem is, it keeps displaying only the first word of the text over and over. I have no ides why it does this. I'm sure it has something to do with my non-understanding of some string functions, but I looked and tinkered with it for like half an hour without fixing the issue. Can someone enlighten me on what is happening here?

Here is the code of the script itself:

Code:

var tempText = argument0;
var tempWord = "";
var tempString = "";
var tempReturn = "";
tempReturn[0] = "";
tempReturn[1] = "";
tempReturn[2] = "";
tempReturn[3] = "";
var tempReturnID = 0;
var tempSpaces = string_count(" ",tempText);
//Init vars
for (var i = 0;i < tempSpaces;i ++)
{
    tempWord = string_copy(tempText,0,string_pos(" ",tempText));
    tempText = string_delete(tempText,0,string_pos(" ",tempText));
    //Cut first word of tempText to tempWord
    if (string_width(string_insert(tempWord,tempString,0)) > 256)
    {
        tempReturn[tempReturnID] = tempString;
        tempString = "";
        tempReturnID ++;
        if (tempReturnID > 3)
        {
            return tempReturn;
        }
    }//If tempString + tempWord > 256 pix, cut tempString to tempReturn[tempReturnID] and increment tempReturnID
    tempString = string_insert(tempWord,tempString,string_length(tempString));
    tempWord = "";
    //Cut tempWord to the end of tempString
}
//Loop through this for every space
return tempReturn;
//Return the array

Then here's my create event:

Code:

///Init
text = "This is a test string and I want to test it! it's really not long enough so I'm going to add a bit of text to this to make it less readable.";
newText = text_get_wrapped(text);

And finally the draw event:

Code:

///Draw text
draw_self();
for (i = 0;i <= 3;i ++)
{
    draw_text(x,y + (i * 12),newText[i]);
}

This is the output on screen BTW:


I hope this is not too much of a request, but I'm really stumped by what the heck is happening... 

[Glyph]

Strings are 1-indexed, and passing 0 to some string functions like string_delete makes them fail. So do this instead:

Code:

tempWord = string_copy(tempText,1,string_pos(" ",tempText));
tempText = string_delete(tempText,1,string_pos(" ",tempText));

[ProgramGamer]

Oh wow. Thanks, This'll definitelly be useful. I guess it makes sense for them to work that way, but there's no indication I saw anywhere that they work like that. I'll check the documentation to verify if I'm freakin' blind or not.

[tinyDino]

OpenFl/ Haxe question here, does anyone know how to automatically find the resolution of the screen the application is running on? I've looked everywhere online and nothing seems to work correctly.

[gimymblert]

can you make a game whose code source can be contain in a single tweet?
http://boingboing.net/2015/06/30/tiny-twitch.html

[ProgramGamer]

I'm going to try that tomorow. Seems fun!

[Dacke]

Python isn't exactly the most terse language, but I made a super simple game in 140 chars.

Code:

import random as r
n=r.randint(1,100);g=c=0
while g!=n:
 g=input("Guess? ");c+=1
 if g<n: print "+"
 elif g>n: print "-"
print "\nWon in", c

[Photon]

What are the performance implications for having lots of static classes composed primarily of functions?

I have a base organizer object that can be set up in a lot of ways but Haxe doesn't support having multiple constructors as far as I know. My thought was then to put "constructor" functions in a static class that would then take the base object as a parameter and more or less attach the child objects that were needed for the desired functionality.

[Dacke]

Sounds a bit like the factory pattern, except then you have an instance of the factory class which can keep track of resources needed to create other objects.

Either way, the overhead should be minimal. An extra function call and some extra code to keep in memory.

[Photon]

I had to look up factory pattern...

I'm not sure if that's what I'm doing, actually. Basically, I have node objects (in a tree) that perform operations on input/output references, if you will. Sometimes one node's output is another node's input. What the static function might potentially accomplish is generating/hooking up the two nodes with matching output/input with the matching reference and add them as children to a supplied parent node. Said parent node can then update them in the appropriate order.

That's a bit of a tangent from the original question I suppose, but it sounds like an interesting tangent to go on.

Anyway, my main concern was whether it would create undue overhead in the future versus, say, normal object-bound functions, since I'll potentially have a lot of these static classes.

[BorisTheBrave]

Yes, it's fine, and not uncommon. See, e.g. C#'s Expression which is doing something similar and uses many "static constructors" (as they are sometimes called).

You may find doing so causes problems with generics (called type parameters in Haxe), which often expect normal constructors. It would be a good idea to keep the zero-agument constructor for that purpose.

[Photon]

I should clarify that the object has already been constructed/initialized by the time it hits the static function. The point in part of the function is to construct the underlying tree structure that will support the functionality. A concrete example:

Say I've got a text display node and a text parsing node. The display node does exactly what it sounds like while the parsing node feeds characters to an output overtime (such as to simulate a dialogue appearing.) The display node's output and the parsing node's input are basically the same reference (in my instance, a data component similar to that found in ECS) for something like a dialogue box. So to automate "constructing" a dialogue field, I'll have a static function that accepts a parent node and some sort of blueprint to do the following:

1.) Create the two nodes and set up their references (per the blueprint specifications)
2.) Hook them up to the passed parent node so it can update them in sequence

Thanks for the feedback. I've kind of tried to stay away from static classes, but that was more because of static variables than static functions. Looks like its worth a shot.