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.
Last edited by Tigairius; 10-06-2010 at 10:08 PM..
Reason: Updated videos
I was waiting for you to click on an area that was inaccessible, to see it explode.
With the example of how it can be used, the soldiers will chat "I can't move there" if I try to move to an area that is inaccessible because the valid locations are predefined. I guess I should've shown that!
Here's a little level sweepage, 3015 valid locations.
As you can see, the area inside the table was not highlighted because it is not valid.
Last edited by Tigairius; 10-06-2010 at 10:08 PM..
Reason: Updated video
Oh, I also forgot to mention that I changed the h-score equation to a revised manhattan equation that takes diagonal movement into account. The equation favors diagonal movement.
Oh, I also forgot to mention that I changed the h-score equation to a revised manhattan equation that takes diagonal movement into account. The equation favors diagonal movement.
I haven't read either but diagonals are very important. My logic used 10 for horizontal/vertical while 14 for diagonal otherwise it took a very long time to reach sometime diagonal from it's point of origin.
On another random note, I found a* algorithms start to go real bad once you're above the 64*64 tile range.... implement a method to work with a node based system? =D (i'm way too lazy)
Oh, I also forgot to mention that I changed the h-score equation to a revised manhattan equation that takes diagonal movement into account. The equation favors diagonal movement.
Neat. Nice work
Quote:
Originally Posted by Twinny
I haven't read either but diagonals are very important. My logic used 10 for horizontal/vertical while 14 for diagonal otherwise it took a very long time to reach sometime diagonal from it's point of origin.
On another random note, I found a* algorithms start to go real bad once you're above the 64*64 tile range.... implement a method to work with a node based system? =D (i'm way too lazy)
It already takes diaganol movement into account, just not in the "h-score".
Diagonal movement "costs" 14 and horizontal/vertical was 10 (1,1,sqrt(2) triangle)...and with A* that would make moving to a diaganol node less favorable because it's considered to be a longer distance. However, if taking a diaganol path will get you to the final location quicker, it still will to a certain extent.
Keep in mind this searches tile-by tile, and doesn't take into account that a straight line to the target might be the quickest approach (like if there's no walls)...might be something else you could add.
Keep in mind this searches tile-by tile, and doesn't take into account that a straight line to the target might be the quickest approach (like if there's no walls)...might be something else you could add.
Bumping this thread a bit...
I've tried several times to have a larger wall checking area than 1x1 and have absolutely no luck. I'm wondering if you've had any luck doing this, Salesman?
__________________
Quote:
*SlikRick: so should I even ask about your aim status?
*Xor: well if you want to
*Xor: but i am LARPING
*SlikRick: While on a computer?
*Xor: yes
*Xor: in my living room
*SlikRick: ahh
*Xor: i have a fort setup to hide from beasts
Bumping this thread a bit...
I've tried several times to have a larger wall checking area than 1x1 and have absolutely no luck. I'm wondering if you've had any luck doing this, Salesman?
What problems are you running into? I used tiles as nodes in this example for simplicity, but when I was working on an RTS server I had it working fine with many different sized nodes.
I'm supposed to be cramming for an exam right now...serious ADD...but I'll try to maybe show an example of larger nodes tomorrow or this weekend.
10-12-2009, 10:20 PM
Linear Mode
