[as3]Making calculations step by step

12 posts

Flag Post

In my game i have multiple objects, which use pathfinding almost always. If i have at least 15 of them, game is almost unplayable – pathfinding calculations are always freezing it for little time, but it is annoying.

A book suggests making an array of calculations and an object(a class), which will go through that array and make some calculations on each element of array. That way everything shall go smoothly and without freezes, as ammount of calculations shall be limited to the number where it wont freeze.

Now, for the questions:
1)What is a good ammount of calculations which game can do without freezing? How can i find it? Obviously, some processors are faster and some are slower, so is there any way to adjust it for each processor?

2)Is it the good way to solve the problem of freezes or is there a better solution? Or did i get the idea wrong and i shall do something else there?

 
Flag Post

I have a hard time understanding how you can have your game freeze with 15 objects doing some pathfinding. It’s not the sort of problem you should be running into before you have hundreds of hundreds of objects.

While there are techniques for doing the calculations “step by step” across several frames, I would instead advice you to find out why the pathfinding is taking up so much resources. Are you continuously recalculating the path every frame? If so, saving the results into the object would lessen the burden several hundred times over.

 
Flag Post

Well, i tested it on a small space, where all of 15 objects would block each others path. Even with them waiting few seconds(to check if path is clear again) before calculating path again they have to run pathfinding algorythm oftenly. So that can be counted as path being countinuously recalculating.

Even if this is an error, there will be problems with hundreds of them. Can you help me on that topic?

 
Flag Post

Are you using an array as your map? Post the path-finding parts of your code here (or pastebin it), and we will see what is taking such a heavy tax.

 
Flag Post
function PathFind(x1, y1, x2, y2, w2, h2)
		{
			var curc = Global.map[x1][y1];
			var dest = Global.map[x2][y2];
			var firstc = curc;
			var f;
			var g;
			var h;
			var maxd = Global.Dist(x1,y1,x2,y2);
			var scan = 0;
			w1 = w2;
			h1 = h2;
			opened = [];
			closed = [];
			curc.g = Global.map[x1][y1].Occupied.length;
			curc.f = ManH(x1,y1,x2,y2);
			curc.h = curc.f
			while (curc!=dest)
			{;
				scan++;
				GetNei(curc.x, curc.y);
				for (var i = 0; i<nei.length; i++)
				{
					var t = nei[i];
					if (t!=null)
					{
						g = curc.g + 1;
						h = ManH(t.x,t.y,x2,y2);
						if (minr==undefined)
						{
							minr = h;
							minc = t;
						}
						else if (h<minr)
						{
							minr = h;
							minc = t;
						}
						f = g + h;
						if (isOpened(t)||isClosed(t))
						{
							if (f<t.f)
							{
								t.g = g;
								t.f = f;
								t.h = h;
								t.Parent = curc;
							}
						}
						else
						{
							t.g = g;
							t.f = f;
							t.h = h;
							t.Parent = curc;
							opened.push(t);
						}
					}
					else
					{
						closed.push(t);
						return BuildPath(minc, firstc);
					}
				}
				closed.push(curc);
				if (opened.length == 0)
				{
					return [];
				}
				opened.sortOn('f', Array.NUMERIC);
				curc = opened.shift();
			}
			return BuildPath(dest, firstc);
		}

The map is 2 dimensional array.
EDIT: GetNei – puts all cells next to curc cell into nei array.

 
Flag Post

A* on a large network can be noticeably slow … to lag your game it only needs to take 30ms, after all, so that’s 2ms per object if you try to do 15 all in the same frame.

Try to break your network and path down into sections so you don’t have to pathfind on the full network every time, particularly if it’s a recalculation due to a broken path, and see if you can have different objects calculate their paths in different frames.

You can spread calculation over several frames (for example here’s how I do that), but if you’re trying to calculate too much, that won’t actually help you. If you’re trying to do a second’s worth of pathfinding once every 15 seconds, though, it will.

 
Flag Post

Not bad, but here is my advice:

1. change to fixed size vectors instead of arrays.
2. use a single vector/array rather than a 2d one.
3. use lists instead of arrays for ‘opened’ and ‘closed’
4. and avoid the expensive array.sortOn function

 
Flag Post

Thank you for your advices, Drakim and BobJanova. I also did a test and noticed, that there are about 120 pathfinding calls for 9 units in no more than a minute. Most of them are for small distance(another object blocked first cell into path), result path is 2-3 cells long. Will any of methods be usefull for that case(well, they will be usefull, but for how much)?

 
Flag Post

A path two or three cells long should be very quick to calculate. Are you sure it’s this code that’s slowing you down?

You should have your GetNei function return the neighbours, not put them in a global variable, and you should localise opened and closed and pass them to your isOpened/isClosed functions. Global state is bad and can get you into trouble. That won’t help your speed issue but it’s a general point.

 
Flag Post

It is not global state. Pathfinder is a class. When i want path to get calculated, i create a new object of that class and remove it after pathfinding is done. So the variables shall not interfere each other, right?

 
Flag Post

Local variables like curc, dest, fistc, f, g, h, maxd, etc, will not interfere with each other if you call this function many times. Only static variables would “interfere” in such a manner.

 
Flag Post

Instance state is less bad but still bad if there’s no reason for it. In such a simple situation it won’t cause you concrete problems, but it’s a bad habit to get into; for example if you move into multithreaded environments this code could break in weird ways if it was run twice in parallel, particularly if several methods use the same instance variables.