Need help figuring out pathfinding

[ForgeableSum]

So I'm trying to figure out pathfinding for my game which is a little different from your typical top-down tilemap game. The main difference is that sprites need to be able to walk around other sprites but the sprites themselves aren't confined to tiles. i.e. a sprite can be any width, any dimension and take up space on as many tiles based on its dimensions and position on the world map.

 

This creates a unique problem because I cannot define tiles as walkable and non-walkable (and therefore, cannot use the famous pathfinding plugin for phaser) ... the sprites themselves need to be walkable and non-walkable. But I honestly don't have the time, inclination or know-how to rewrite the plugin for sprites. I understand the advanced math behind pathfinding - so, my first plan was to create a fake tilemap layer the plugin could use with really small tiles. The game would update the tiles as walkable, non-walkable whenever a sprite moved ... the idea of the really small tiles was to be able to accommodate any size sprite with a multitude of tiles (5 x 5 tiles would work if the smallest sprite was 10 x 10). This, of course, proved to have major performance issues (just try making a tilelayer with tiles 5x5 and the width/height of the layer being 1000/1000)!  so I'm now of the opinion it's not a viable option for pathfinding. 

 

I think, however, if I overlayed a JS grid system of some sort (instead of using a fake performance-heavy tilemap layer) which translated to the tilemap matrix the pathfinder plugin uses, it could work. But I don't know. To be honest, I'm completely confused, and running around in circles.  I would appreciate any help/direction from those more experienced than me. Thanks!

[cdrch]

I wouldn't consider myself particularly experienced, in either pathfinding or Phaser, so take what I say with a grain (or two) of salt. But I've spent the last week puzzling over pathfinding solutions myself, so here's what springs to mind.

 

Assuming you do want to use A*, I think you'd definitely be better off just overlaying a plain 2D array (or similar structure) onto your game, either of objects that contain all of the necessary pathfinding information or several arrays of integers (or whatever) that each contain one part of the necessary information (walkable, additional G cost, etc.) In other words, exactly what you are thinking. If you need to extract information from the tilemap to use, then it shouldn't be too hard to find what tile lies under a particular node with getTileXY() and get the info that way.

 

With different sizes of sprite, you'll need some way to mark the nodes differently for each sprite. Having the sprite update all nodes to accommodate its size sounds pretty slow to me; I think it would be better to actually have different grids for each size of sprite or have multiple values on one grid that the pathfinding can choose from based on the size of sprite. I haven't worked with EasyStar.js (or its Phaser wrapper), but I would guess that you would need to have multiple instances of it in order to deal with the different grids, or else constantly be calling setGrid(), which seems like a bad thing to me. (Could be wrong!) You probably could modify it to be told to check different walkable values, but I wouldn't know where to start.

 

You'll also need to have sprites telling all of the grids what space it is taking up.

 

Just so I know I'm communicating clearly, have a picture. Imagine 'D' as a hazard, with 'C' sprites being a tile large, 'B' sprites being two tiles large, and 'A' sprites being three across. Of course, they could be any size, so long as they aren't any bigger than that size. In the image, each tile is marked with the letter of the smallest sprite it is walkable for. Sprites of type A would use a map where B, C, and D are all unwalkable, B Sprites, would use C and D, etc. Just inflate hazards by the radius of the sprite (or an imaginary circle surrounding a sprite, anyways) and imagine the sprite as a point.

 

[ A | A | A | A | A | A | A | A ]

[ A | B | B | B | B | B | B | A ]

[ A | B | C | C | C | C | B | A ]

[ A | B | C | D | D | C | B | A ]

[ A | B | C | D | D | C | B | A ]

[ A | B | C | C | C | C | B | A ]

[ A | B | B | B | B | B | B | A ]

[ A | A | A | A | A | A | A | A ]

 

That's about as good a solution as I can think of that doesn't require writing an implementation of A* from scratch, manually setting up several node maps to allow for movement, or things like visibility graphs or potential fields. I'm probably going to start using EasyStar.js soon, since my current pathfinding plugin appears to be bugged, so I'll come back if I come across a solution that might be of more use to you.

[ForgeableSum]

Using phaser's native functions for tiles to update the pathfinding matrix, I think, would cause too much of a performance cost, especially if you have a lot of sprites. I think tilemaps really should just be used for tilemaps. But  it's beginning to come together for me. I've been thinking about it the wrong way. There's no need to render a graph (with a tile layer) on top of the game world so long as the dimensions of the matrix parallel the dimensions of the game world exactly.

 

Suppose we have a world size of 100 x 100 pixels. We can divide the pixels into tiles with a pixel dimension of 5 x 5 and create a matrix that is 20 x 20. Each node in the matrix represents a tile that is 5x5 in the game world. 

 

When a sprite arrives at a destination in the game world, we can determine which nodes the sprite falls on in the matrix. For instance, if the sprite is 10 x 10, modular, and the top left x/y of the sprite lands on 45, 32 in game world coordinates, we can determine which matrix nodes the sprite is sitting on by evaluating the following coordinates in the case of (45, 32):

top left: is (45, 32)

top right is (55, 32)

bottom left is: (45, 42)

bottom right is (55, 42)

 

Translate these coordinates in the matrix by dividing by 5 (since matrix to real world is 1 to 5) and you have to set the following nodes as unwalkable:

(9, 6.4)

(11, 6.4)

(9, 8.4)

(11, 8.4)

 

Round these numbers down because we want the whole tile the sprite lands on, not exactly where on the tile the sprite lands on. So there you have it, the following nodes in the matrix are set to unwalkable:

(9, 6)

(11, 6)

(9, 8)

(11, 8)

 

Then every time a sprite moves, you remove whatever tiles the sprite took up in the matrix. I'm not sure if easystar.js has a function for updating the matrix in real time. I think it's designed for games which have walkable/non-walkable tiles (i.e. the walkable and non-walkwable areas never change during the course of the game, but that doesn't suite us). PathFinding.js, the one I've found today does have a function for updating the matrix in real time:

https://github.com/qiao/PathFinding.js/

 

grid.setWalkableAt(9, 6, false);

grid.setWalkableAt(11, 6, false);

grid.setWalkableAt(9, 8, false);

grid.setWalkableAt(11, 8, false);

 

Also, when you create the matrix, you don't need to supply a literal matrix with nodes represented by characters, all you would need to do is provide the dimensions:

var grid = new PF.Grid(20, 20);

 

That saves a lot of time. 

 

If each matrix node represents 5x5 in the game world, I think it could accommodate any sprite size, so long as the smallest sprite is something like 10 x 10. Actually, the node size in the matrix should be whatever number of pixel padding you are comfortable with. In the above example, the 6.4 and 8.4 tile still have 60% of the tile not filled by the sprite. That translates to 3 pixels (5 x .6) extra space that isn't walkable but should be walkable (since the sprite doesn't exist in that portion of the tile). It's still pretty accurate though and if you wanted it to be more accurate (at a cost in performance), you could make the 5 x 5 smaller. 

[cdrch]

Using phaser's native functions for tiles to update the pathfinding matrix, I think, would cause too much of a performance cost, especially if you have a lot of sprites. I think tilemaps really should just be used for tilemaps.

What I meant was just if you wanted to transfer information from a tilemap's properties once, if you prefer to design your levels in an editor. Doing it repeatedly would probably be unwise.

 

Looks like your solution should work. Nice find on Pathfinding.js; I may just follow your lead, since a dynamically updating walkability map is growing more important to me. I was nearly going to mention that you should round up on those numbers, but you addressed that in the last paragraph. You should post back here to let us know how it works out!

[ForgeableSum]

What I meant was just if you wanted to transfer information from a tilemap's properties once, if you prefer to design your levels in an editor. Doing it repeatedly would probably be unwise.

 

Looks like your solution should work. Nice find on Pathfinding.js; I may just follow your lead, since a dynamically updating walkability map is growing more important to me. I was nearly going to mention that you should round up on those numbers, but you addressed that in the last paragraph. You should post back here to let us know how it works out!

 

Cool. Here's a function I wrote for translating a sprite's world coordinates to matrix coordinates with any matrix node size. Note that you need to set the body width and height of the sprite with physics enabled on the sprite. 

function setSpriteUnwalkable(sprite) {        var matrixNodeSize = 5;        var xDistance = sprite.body.width / 2;        var yDistance = sprite.body.height / 2;        var topLeftX = roundDown(sprite.x / matrixNodeSize);        var topLeftY = roundDown(sprite.y / matrixNodeSize);        var topRightX = roundDown((sprite.x + xDistance) / matrixNodeSize);        var topRightY = roundDown(sprite.y / matrixNodeSize);        var botLeftX = roundDown(sprite.x / matrixNodeSize);        var botLeftY = roundDown((sprite.y + yDistance) / matrixNodeSize);        var botRightX = roundDown((sprite.x + xDistance) / matrixNodeSize);        var botRightY = roundDown((sprite.y + yDistance) / matrixNodeSize);console.log('(' + topLeftX + ',' + topLeftY + ')' + '(' + topRightX + ',' + topRightY + ')' + '(' + botLeftX + ',' + botLeftY + ')' + '(' + botRightX + ',' + botRightY + ')'); grid.setWalkableAt(topLeftX, topLeftY, false); grid.setWalkableAt(topRightX, topRightY, false);grid.setWalkableAt(botLeftX, botLeftY, false); grid.setWalkableAt(botRightX, botRightY, false); }

And of course, don't forget to set the matrix width/height:

        game.world.setBounds(0, 0, 4000, 1500);        var gridWidth = game.world.width / matrixNodeSize;         var gridHeight = game.world.height / matrixNodeSize;         grid = new PF.Grid(gridWidth, gridHeight); 

All that's left to do now is:

* run this function for all sprites at the creation of the game (or when a new sprite is created)

* run this function whenever a sprite arrives at a new location.

* run a function which resets unwalkables back to walkables whenever the sprite moves 

* run a function which translates the matrix node coordinates (fed to it by the function for finding a path) into game world coordinates and moves the sprite accordingly. 

 

I'll report back on my progress!

[ForgeableSum]

Update: it worked!

 

I did run into a few problems though, the biggest one being that the matrix size never parallels the game size exactly because pathFinding.js is written in such a way that you can't set both extremes of the x and y axis. So if the grid size is 3 x 3, you can't set any coordinate with a '3' in it... this threw me off a lot because I kept getting errors whenever I tried to set x/y extremes walkable.

I think the grid size should be + 1 to accomodate 0 and both extremes of the x/y axis (i.e. if the grid size is 3 x 3, the array size should be 4), but the creator didn't agree with me.

More on that: https://github.com/qiao/PathFinding.js/issues/85

 

Even if I do make the grid + 1 (1 more than the game size x and y) I get errors though, because I'm rounding down and dividing when converting real world coordinates to the matrix and vice versa. As a result, I will sometimes end up with values below zero. So in the same function that checks for invalid nodes, I'm checking for coordinates below 0 and setting them to 0. 

 

Anyway, other than scripting workarounds for game world coordinates that don't exist in the matrix and vice versa, I didn't run into any major issues. I'm debugging the grid with jQuery: creating tiny float left divs to visually represent the grid. Of course it's super slow with jQuery debugging but it suites my purposes when I need to see where a sprite lands on the grid and where walkable/notwalkable nodes are in the game world. 

 

One problem with pathFinding.js is that each time you find a path on the grid, you need to recreate the grid to find a path on it again. I haven't really explored why this is. I suppose the pathfinder needs to set property values in the grid matrix to work. I haven't looked for a workaround to recreating the grid each time I need to find a path. Worse case scenario, it doesn't affect performance significantly if done right. 

 

I'm now working on developing two pathfinding 'modes':  local and global. a sprite is visible on the screen, I'm going to generate and loop a local grid of just the coordinates in the matrix which appear on the screen. If the sprite is traveling to a location not in the current window, I'm going to use a different grid mode, (global) one that is created from all nodes (instead of just a segment of nodes). This will save tons of memory, not having to loop through all nodes every time.