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.

[Jcs1919]

You so pro !

[DustyPorViva]

I was waiting for you to click on an area that was inaccessible, to see it explode.

[salesman]

Originally Posted by DustyPorViva

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.

[fowlplay4]

Originally Posted by salesman

Youtube

That was awesome.

[Pelikano]

wow nice

[coreys]

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.

[DustyPorViva]

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

[coreys]

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.

[Twinny]

Originally Posted by coreys

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)

[salesman]

Originally Posted by coreys

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

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.

[Chompy]

Originally Posted by salesman

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.

[coreys]

Originally Posted by Chompy

Using onwallpath() could fix that.

Que es eso?

[coreys]

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?

[salesman]

Originally Posted by coreys

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.

[coreys]

I think I was just going about the problem wrong before, I wasn't adjusting the grid, instead I was adjusting the onwall detection, when I should be doing both.

Honestly I'm not sure, I haven't used this in awhile, but I seem to remember my edit that allowed variable size nodes not working properly.

[salesman]

Originally Posted by coreys

I think I was just going about the problem wrong before, I wasn't adjusting the grid, instead I was adjusting the onwall detection, when I should be doing both.

Honestly I'm not sure, I haven't used this in awhile, but I seem to remember my edit that allowed variable size nodes not working properly.

I think my OP kind of implied that all you had to do was modify the onwall checks to find paths for larger objects (which is NOT the only thing you have to do). My bad! I'll release an updated version with variable node-size support hopefully by this weekend.

Edit: Here ya go. It seems to work, but I kind of rushed through it so let me know if you run into any problems.
findpathnew.txt

Added two more parameters.

• nodeSize -- array, width and height of the size of the object looking for a path in tiles (for example {2,2})
• moveByNode -- boolean, set this to false if you want to still search tile by tile (explained below). When false, your grid will be the tiles that make up a level, when true your grid will be made up of nodes of size "nodeSize"

findPath(cx, cy, tx, ty, nodeSize, moveByNode, cutCorners, fullPath)
Example of usage:

PHP Code:

findPath(player.x, player.y, temp.targetx, temp.targety, {2,2}, false, true, false);
// This would search for a path from the player's location to a target location, taking into account the size of the player (2 tiles by 2 tiles) and allowing corner cutting 


Here's an image searching for a path for a 2x2-sized object on a node-basis (white is the full path, black is the important nodes, the rest is just nodes that were searched):


It also allows you to search for nodes smaller than 1 tile, but I can't really see a reason why you'd ever want to do that:


Ideally, you probably want to set moveByNode to false. Otherwise you might not find a path that actually exists. Here's what I mean:


In this picture, the gray lines represent tiles. The black lines represent what your grid will look like with moveByNode set to true. The green squares are starting and finishing nodes. The red is a wall. The pink is a spot that should be a perfectly fine spot for a 2x2 object to sit, but would not be considered fine if moveByNode is true. With moveByNode set to true, the path from one green to the other is impossible because it searches by node (black squares). When false, the path is found easily.

An example of when you might use moveByNode is for a turn-based system where NPCs can only move a certain number of nodes and/or maps are designed based on the node/object-size.

[salesman]

sorry for double posting, but I forgot editing the last post doesn't bump the thread and I want coreys to know that I updated the script.

[coreys]

Thanks. This will come in handy.
However, moving this script to serverside I've noticed it takes quite a bit of CPU usage (at least serverside, it does).

Also, you may want to add some sort of offset option, for cases like a normal player character type NPC where the top of the head doesn't need to be counted as a blocking area.

Additionally, this paper might be interesting to you! It's basically on how to efficiently find paths with variable size entities; it also has a lot on dealing with multiple types of terrain where entities have certain types of terrain they can clear but that's probably not that important (unless you want it to be!).