What does this mean for me? You will always be able to play your favorite games on Kongregate. However, certain site features may suddenly stop working and leave you with a severely degraded experience.
What should I do? We strongly urge all our users to upgrade to modern browsers for a better experience and improved security.
We suggest you install the latest version of one of these browsers:
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?
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.
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?
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](http://www.redcorona.com/flash/backgroundtasks.html)), 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.
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
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)?
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.
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?
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.