findPath()

[salesman]

I never planned on sharing this with anyone when I made it a while back, but since you asked....

I strongly suggest you read this tutorial which helped me understand A* pathfinding. I must have read it at least 5 times myself while coding this. There's also several suggestions on how you can help speed up your pathfinding.

findPath(cx, cy, tx, ty, cutCorners, fullPath); -- returns an array of nodes (tiles) from one tile to another

• cx - starting x location
• cy - starting y location
• tx - target x location
• ty - target y location
• cutCorners - boolean, should the path be allowed to cut corners?
• fullPath - boolean, return the path as an array of nodes on a tile by tile basis? If false, the function will only return an array of important nodes, or "turning points" for the path.

Source:
findpath.txt
It's not commented very well...I added what I could quickly before posting. It actually wasn't commented at all until today, so if you have any questions just ask.

For example,

PHP Code:

// will return a list of important nodes without corner cutting
temp.nodes = findPath(player.x, player.y, 30, 30);

// will return a full list of nodes allowing corner cutting
temp.nodes = findPath(player.x, player.y, 30, 30, true, true); 


Video:


Important note:
This function assumes that the object you are finding a path for is only 1 tile big (16x16 pixels). However, it shouldn't be hard to modify the onwall checks for bigger objects such as a player. I might add another parameter for the size of the object in the future, but I don't have the time right now.


Tips for improving speed:

• Predefine invalid locations such as areas that are non-blocking tiles, but completely surrounded by blocking tiles and therefore inaccessible. The easiest way to do this is to search for a path, but do not break the loop when a path is found, so that the loop will not stop until all nodes have been checked. "Valid locations" will be the closed list. It's as simple as removing one line of code!
• Implement a queue when multiple objects are searching for paths. Make them wait their turn!
• Predefine difficult or large paths, and then find a path to a point on the predefined path.