A-Star test proggy

[Naughty Alien]

..im looking for some decent example (EXE) of A-star, in order to properly benchmark small lib i have made for Tutorial lessons of mine..do you guys know any similar program, executable, that i can download and set some conditions (eg. number of nodes to search, start/end node..), in order to do proper benchmarking, speed wise.. everything i found is slower than my lil lib, but i dont want to accept that as a final, since many of them are java applets and they are suckers, on other some seems to be very basic form of A-star with no optimizations, so i really cant take those as a valid reference..im looking for something considered very fast..if you know any, please, post download link so i can take it and do some tests before release lessons..thanks in advance guys..

[cocopino]

This page:

http://www.policyalmanac.org/games/aStarTutorial.htm

 

has a couple of test programs with source code at the bottom, is that useful?

[Naughty Alien]

..i have seen this..both versions are slower than mine so im looking some sort of 'pro' test proggy, if i may call it that way..

[Pixel Perfect]

I don't know of any exe progs you can download and just run but you could quickly knock something up using micropather in C++. If you have already existing node data it should be pretty easy to populate this.

 

I have no idea how fast this is though!

 

To be honest I suspect your routines are already fast enough, I wouldn't worry about ensuring its faster than everything else out there! So long as it can resolve paths efficiently for structures similar to the diagram underneath (green is start position, red is target) then it should be fine. You would of course be using a lot more nodes than the diagram

 

grid.bmp

[Naughty Alien]

..i found out that more than 3900 searchable nodes are more than enough on my levels (considering distance between nodes approx 10 meters) its about 625x625 meters area..but even that is sometimes not necessary, if path is NOT as a rectangle shape, what is most of the time case, so i noticed, generator extract roughly up to 1000 nodes max, for custom shape levels whats very nice and handy for search algo..also, its possible to have independent groups of search nodes in order to release pressure from search routine, so it can be search by zones..all this tests are a bit confusing for me because im getting quite nice results, and i dont feel comfortable when i see no obstacle..thats why I wanted to try something out there, considered very fast, as a benchmark..

[Pixel Perfect]

..i found out that more than 3900 searchable nodes are more than enough on my levels (considering distance between nodes approx 10 meters)

That might be true for low density geometry scenes but how are you going to find your way through many floors of densely populated buildings for example full of obstacles?

[Joh]

Do you use Navmesh? Also do you have many not-static obstacle (npc, veichle, etc..)?

An A* can be optimized to suite many of your needs, so i need more infos to give you something good.

[Naughty Alien]

That might be true for low density geometry scenes but how are you going to find your way through many floors of densely populated buildings for example full of obstacles?

..well, as I said, not all output navmesh shape is rectangular, and way trough door doesnt require more than 2 major nodes..also, it almost doesnt make sense to populate nodes just about 1 meter away from each other, unless its small tiny space, what is okay, because its small ..and even then as I said, each floor can have its own nodes grid generated (not connected to others), so search is performed at actual area what is much faster than one bigger nodes grid..second thing is that actual walkable nodes are generated over navmesh without considering crates or other obstacles eventually appear , so such check is done over path returned , and when critical node is reach, just new path search is performed to avoid that small obstacle (faster than calculate everything from start point)..thats something i do, but everyone can have different way of doing things..I have seen some commercial games and nodes populated for pathfind in them and its really not that high density..its actually quite low..thats why I wanted to see some benchmark test, if any..

[Pixel Perfect]

I kind of know what you're saying NA as my system too is a hierarchical based system and I too can split the search down into smaller zones but at the end of the day the node density is determined by the density of objects that need to be avoided and that doesn't neccessarily imply that high density areas are going to be small as you were suggesting, that is really down to the level design and the game's environment. The node numbers have to grow with increasing geometry density. The shape as you say is pretty irrelevant!

 

I understand you wanting to test your system against others but what is more important from my findings is the type of tests you do rather than just comparisons between different A* systems. Because they will all perform well against simple search paths. Anyway, good luck with your testing. I've tried searching for any available executable systems that might be useful to you as a comparison and failed to find anything. There seems to be very little out there!

 

It does sound like an interesting system you have there and I'm looking forward to seeing more detail when you release your tutorial. I didn't bother optimising mine much as it runs more than fast enough for my own needs but I'll be interested in seeing how you've approached this.