Pathfinding and Map Wrapping rants

Okay, here is the rants about Pathfinding and Map Wrapping in Ocean Horizons,they are royal pains really, why? Let me explain:

Pathfinding on HUGE tiles map:
Initially I naively thought a decent pathfinding algorithm will solve the problem, so I ripped borrowed A* Array implementation codes from an excellent pathfinding example program called PathFinder2D, but soon I realized pathfinding on a HUGE tile map will be a CPU hog, not to mention the enormous overhead of memory used by PathPlanner to store tile information like block status, open/closed flag, terrain type and stuff.

I have to make a simple and stupid pathplanner that only plans next node to move towards, basically it loops through 8 directions and find the one that is closest to the destination, it sucks but works.Probably a last-node needs to be passed to that function to avoid lock between 2 tiles.

Additionally a navigation graph needs to be incorporated into pathfinding system, once the graph is contructed, the routes between nodes are trusted, which means there is no obstruction between 2 linked nodes in graph, so pathfinding is not needed when doing long distance traverse.

Map Wrapping:
What is Map Wrapping?You may wonder, Map Wrapping is wrapping the coords when reaching map edges, it's a must because planet Earth is not flat, at least in our game. So whenever the map reaches edges(MAX_WIDTH or MAX_HEIGHT), the map needs to be wrapped to X-0 Y-0 again, this sounds easy enough, but there is tons of stuff that need to take Map Wrapping into consideration:

When units move to a coordination that is larger than max x, max y, you will need to cap it.
When screen draws tiles x, y bigger than max x, max y, you will need to draw the wrapped ones.
Distance between tiles calculation must checkwhether the distance is greater than 1/2 of map height or width, because distance between X-1023 and X-1 is actually 2 on a 1024 width map, but you might get broken result 1023-1 if you don't..

Hopefully I will be able to resolve these headaches gracefully. =D

No comments: