0
\$\begingroup\$

I'm trying to make a game at the moment and have some trouble with the A* algorithm for path finding.

enter image description here

In the picture the orange and rainbow cells are walkable, but the orange cells have walls around them that should not be crossed. I don't know how to define these walls for my A* algorithm.

So my player is going over the wall to get to the point (red path) but I want it to avoid the wall (green path).

I'm currently using this library: astar-javascript but I can't define "special" cells with it that could be crossed on one side only.

If anyone has an idea, thank you :)

\$\endgroup\$

2 Answers 2

Reset to default
2
\$\begingroup\$

Two cells are connected iff they are adjacent and there is no wall between them. After that, A* works as normal.

If your path-finding library doesn't support defining adjacency like that (which seems unlikely, they usually support generic graphs), you can use this trick to turn thin-walls into full cells.

\$\endgroup\$
1
  • \$\begingroup\$ Or heck, you can use raycasts to find the walls and populate a datastructure that handles adjacency with the results. \$\endgroup\$
    – Draco18s no longer trusts SE
    Commented Jul 17, 2017 at 14:29
2
\$\begingroup\$

This library appears to use an adjacency matrix, with a value of 0 denoting a wall. See this line in the library's readme:

  1. A weight of 0 denotes a wall.

What you want then in order to denote a wall between cells 1 and 2 is a matrix where matrix[1][2] and matrix[2][1] are both 0. More documentation for the adjacency matrix model is easily accessible online, but I cannot easily link it as I am on mobile.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .