findPath()
 

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:
Attachment 49606
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,
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.

You so pro !

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.

That was awesome.

wow nice

I edited your script so that use takes an offset x/y and width/height for wall checking.

The function parameters now goes as this:
findPath(cx, cy, offSet, blockSize, tx, ty, cutCorners, fullPath)

Where offSet and blockSize are two-member arrays.

It's not perfect, but it does work pretty well.

I would much prefer if a path is not found the characters head exploded.

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)

Neat. Nice work

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.

Using onwallpath() could fix that.

Que es eso?

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.