More speed for FINDPATH function?

Previous topic - Next topic

Hark0

Hi... I'm using FINDATH function in my project.

Works very well, and in my test on iOS devices no have any problem on speed...

But... testing on Win32 computer when I call the fucntion its "pause" the app for X milisecs... Its normal due the calculation of a valid solution for the map.... but...

Any trick for accelerate this function?


Any comment are VERY apreciate.

;)
http://litiopixel.blogspot.com
litiopixel.blogspot.com - Desarrollo videojuegos Indie · Pixel-Art · Retroinformática · Electrónica Development Indie Videogames · Pixel-Art · Retrocomputing · Electronic

kanonet

I played around with FINDPATH() a bit, 'cuz i created my own: http://www.glbasic.com/forum/index.php?topic=5450.msg43705
My one is slower (except very short paths) so this wouldn't help you, but what i learned about Kitty's FINDPATH() is:
Debugmode slows it down very hard! So disable debug, if you need speed. And of cause, smaller maps/paths can speed up your search.;)
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64

Hark0

Thanks for the answers!

I looked code of kanonet but  I use a matrix of 1024x1024 tiles... the size of the map... and I not dicard use more large size of map...

I think a trick using only a piece of the map showed in screen for FINDPATH fucntion.

What do you think?

TIA, Hark0
http://litiopixel.blogspot.com
litiopixel.blogspot.com - Desarrollo videojuegos Indie · Pixel-Art · Retroinformática · Electrónica Development Indie Videogames · Pixel-Art · Retrocomputing · Electronic

Wampus

A piece of the map? Hmm. I wouldn't know how the actual PATHFIND() routine itself is coded but A* pathfinding in general can be sped up a lot if you break up your map into large chunks. Is that what you mean?

If you break into chunks, on any particular search you don't have to calculate the path through the entire map but just through the chunks themselves to see how to get to the one you want to go and from within the chunk you are in at the time of the search. If you get my meaning then you'll see that instead of running PATHFIND() once its necessary to run it twice but its much quicker on both occasions.

Please note that doing the above results in a search that is no longer admissible, i.e. it (most likely) won't find the fastest possible route. However, it will get very close to fastest route possible and will look natural enough. That should be adequate, especially if you need to keep your pathfinding quick.

If you wanted to have a go writing your own pathfinding routine I found an article by a guy claiming his version of A* pathfinding is 300 to 1500 times quicker than the conventional method: http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527

I haven't tested his method for myself but a claim like that did interest me. I mean to give it a try at some point.

Hark0

Quote from: Ragaril on 2011-Jan-29
A piece of the map? Hmm. I wouldn't know how the actual PATHFIND() routine itself is coded but A* pathfinding in general can be sped up a lot if you break up your map into large chunks. Is that what you mean?

If you break into chunks, on any particular search you don't have to calculate the path through the entire map but just through the chunks themselves to see how to get to the one you want to go and from within the chunk you are in at the time of the search. If you get my meaning then you'll see that instead of running PATHFIND() once its necessary to run it twice but its much quicker on both occasions.

Please note that doing the above results in a search that is no longer admissible, i.e. it (most likely) won't find the fastest possible route. However, it will get very close to fastest route possible and will look natural enough. That should be adequate, especially if you need to keep your pathfinding quick.

If you wanted to have a go writing your own pathfinding routine I found an article by a guy claiming his version of A* pathfinding is 300 to 1500 times quicker than the conventional method: http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527

I haven't tested his method for myself but a claim like that did interest me. I mean to give it a try at some point.

You're right. I've been thinking about chopping the map into smaller sections ... and applying FINDPATH function in these pieces of map ... operate over short distances may not have much complication, but I think I will not get good results for long distances within the map.

I'll take a look at the link you mention.

Thanks! ;)
http://litiopixel.blogspot.com
litiopixel.blogspot.com - Desarrollo videojuegos Indie · Pixel-Art · Retroinformática · Electrónica Development Indie Videogames · Pixel-Art · Retrocomputing · Electronic

Hark0

Finally I found the "solution" to my problem.

I opened old version of the same project.

It's run perfectly using FINDPATH function...without any kind of pause... due the differences in two versions of the same project I disabled ALL other subs/functions and I only run render and mouse trap events on main bucle...


About more than one hour of examining and comparing sources I not found any difference on routines affected... BUT...

I look on map declarations sub.... one have this:

REDIM MAPA_Datos_Matriz[0]                  //Clear data map
REDIM MAPA_Datos_Matriz[255][255]

and the other (slow findpath) have:

REDIM MAPA_Datos_Matriz[0]
REDIM MAPA_Datos_Matriz[1024][1024]


You can view the difference... one matrix are 255x255 cells and the other 1024x1024... The size of the matrix are by x4!!!.

Other matrix I have reduced are for the solution#[], initially 1024 and now only 128... I'm considering to reduce to 64 only... are the steps of the path in the map.

:D

Another question... for maps like the image... which is the best value for heuristic#?



TIA, Hark0
http://litiopixel.blogspot.com
litiopixel.blogspot.com - Desarrollo videojuegos Indie · Pixel-Art · Retroinformática · Electrónica Development Indie Videogames · Pixel-Art · Retrocomputing · Electronic

Wampus

#6
By the looks of that map a heuristic of 0.0 (shortest path) would be best. In fact, I'm not sure that setting a heuristic above 0 is a good idea. Its meant to find the path of least cost but in my testing heuristics of 0.5 and above actually result in typically longer paths that cost more than heuristics of 0.0! I really should report it as a bug and create some example code. Anyway, you don't need to worry about that because it looks like the walkable tiles in your game will all be traversed with the same cost/speed. :)

Incidentally, about reducing the map size being quicker, well sure it will! Having a much smaller search area will massively increase the speed of an A* pathfinding algorithm (which is what PATHFIND() is).

Check out this video here: http://www.youtube.com/watch?v=FNRfSQDF7TA

You can see from the above that A*will end up searching a very wide area in order to find its goal unless the goal is close by. Line of sight also matters, depending on the type of heuristic you're using. Regardless, a smaller search area be quicker. Having few or no large open spaces within the map to be searched will also be quicker since that naturally restricts the search area too.

For real speed on a large map you definitely need Hierarchical A* Pathfinding. That's the proper name for what I was trying to explain as making your map "break into chunks". Its also more complicated though and works best if there are choke points of 1 tile, like corridors or doors, that can naturally divide up the map into discrete areas. The reason to use it if possible is its so fast that you could conceivably use it on a very large map with many AI agents doing pathfinding searches without being too CPU expensive. So long as you stick to 4-way directions its possible to use PATHFIND() with it too without having to create your own A* routine.