findPath()

[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!).