Then search each tile to see if there is an entity, chest, or some kind of blocker (ie a wall). Do an outward search from my own maintained grid, grabbing all tiles up to 3 squares away. I also want to highlight enemy tiles that can be reached a different color, interactive items (like a chest) a different color, etc.Ĭurrent Solution: Maintain my own grid, that is a 1:1 grid with the existing gridgraph. Scenario 2: I have a hero, it is his turn, I want to highlight all the tiles that he can reach that are 3 squares away. All other unwalkable nodes are still accounted for in the pathing system. Suggested Solution: Create a new override StartPath function such as: Call StartPath(startpos, endpos, endPosWalkable = true), where the endpos given finds the nearest node, regardless of wether or not it is walkable, and paths to that node. Call StartPath, grab the array of path nodes, and remove the last node from the array.

Scenario 1: I have a hero who is X squares away, and he needs to path to an enemy.Ĭurrent Solution: Find the enemy who is the target, make his node walkable. Let’s think about this like a chess board, where we have an 8x8 grid, and each square that a piece is standing on, is unwalkable. This graph is called 'visibility graph', I believe.Ok, that’s a good point let me clear it up Next construct a graph out of these points by adding edges: For each pair of nodes, check if the two points can be connects by a straight line without hitting an obstacle (ray casting), if so, add an edge between the two nodes.

The start and end point of the path are not in this set of nodes, so add these two, too. For round obstacles you would have to discretize them using polygons. Instead you only need all nodes at wall corners (assuming the player has a radius of zero). For the shortest path, all the 'internal' grid nodes are not needed. There are algorithms for finding the true shortest path in a 2d area of polygons:įirst remove the underlying grid. The kink-path seems to be the shortest possible one on the grid. The kink is there, because at the corner, there is not grid points. Ragzouken wrote:you can see the top path sadly has a kink in it, but it's quite a lot better than what I was doing before. Here's what I'm currently looking at - ideally I'd want to turn that path into an approximation of the actual shortest path if there were no grid. I thought you might have useful input since you seem to know a bit about pathfinding problems! My current thought is look at sets of three consecutive points and see if the ends have line of sight to each other, but I'm not sure this would give great results every time and I probably need a strategy to subdivide straight paths (e.g in the image below you can see it wouldn't work for the top three points because they don't have line of sight). Not sure the best way to achieve this, if there even is a good way to solve it. One way of looking at it is that I want to allow any kind of movement between nodes that isn't blocked by a wall, rather than only allowing the eight compass directions.

I'm wondering if you can provide any input to a problem I'm trying to solve - I want to try and smooth the path afterwards. Hey, thanks again for this it's really nice to have a simple and fast pathing thing to drop in.

Unwalkable nodes