Please note that all screen shots displayed in this blog are works in progress and in no way represent the appearance of the final game. Check out the main site here.

Be sure to follow us everywhere with these links!



Tuesday, June 21, 2011

The no path problem

So I've fully integrated the Dijkstra's algorithm into the game for enemy movement and it works REALLY well, but I have a problem. The algorithm doesn't have any parameters for when no path can be found, and is only appropriate for when there is always guaranteed a path from start to finish. In my case, this is not always so.
For the purpose of getting it working inside the engine I mocked up a simple solution to the problem, but when running the algorithm (with my fix) on a large group of monsters, most of which whom can't find a complete path to their endpoint, it causes big problems in terms of speed; sometimes taking up to 45 seconds to do the thinking for all of the in-game monsters. This will not do, so I need to come up with a better fix (to be fair, my original fix was REALLY haphazard, so I'm not surprised that it sucks balls)
When there IS a clear path from start to finish, the algorithm is solved as quick as lightning, and there is barely any delay to be seen, but I need to be less lazy and more clever to try and sort this thing out.

I'll get there eventually...

No comments:

Post a Comment