CODEWITHSUNDEEP
javascriptshortest-pathpath-findinggame-developmenta-star
kyle
kyle

Reputation: 73

Pathfinding between obstacles that sit on top of walkable tiles

Take the below picture as an example. Consider the following -

enter image description here

The intended behavior here is -

  1. Walking to the orange square results in a straight downwards line
  2. Walking to the pink square (from the blue square) walks around the black squares in close proximity

My current implementation takes a grid of tiles and hands it off to a typical A* algorithm for the shortest path to each square. However, just because a tile has a wall on it does not mean it's unwalkable - it should mean that the generated path does not clip through an object.

That being said, the current implementation results in this as I have no choice but to stick to a 4x4 grid of tiles, and without marking the entire tile as unwalkable, it'll clip through objects. Red tiles being unwalkable.

enter image description here

Which provides a very janky pathfinding system as it'll skip perfectly fine tiles (indicated in red). My question is, how do I make it so the walls aren't clippable, but the tile they sit on is still walkable?

Upvotes: 1

Views: 472

Answers (1)

Federico Rossi
Federico Rossi

Reputation: 413

Idea for a solution:

The first solution obviously would be to increase A* accuracy by having each tile of 1x1.

Another idea is to don't use a simple int grid (or similar) when checking if a tile is walkable. Use instead a function or a more complex data structure that use starting and ending tile to know if that route is available. In such a scenario each 4x4 tile has four possible route (east, north, west, south) and for each one you must know if it is walkable. If you allowed diagonal movements than you would to store/compute 8 routes for tile.

I can't give you more detailed answers since you didn't showed anything of your implementation.

I hope I was helpful

Upvotes: 1

Related Questions