2 added 4 characters in body
source | link

I would prefer to reuse the data structure you already have. So basically a 2D grid that is the floor with a bunch of entities that are put over it.

A* actually works over a graph, so the trick is to make a decent abstract programming interface (API) for a graph. 2D or 3D grid A* is a trick by implicitly converting a grid into a graph with the shape of a lattice graph, where the nodes correspond to the cases of the grid and where the edges connect neighbouring cases of that grid.

In thisyour modified graph,

  • EachLike a lattice graph, each case of the floor is a node, connected to its four neighbours "by default".
  • EachHowever, each entity/object is also a node, connected to neighbour entities provided they have sufficient height so a character can walk across.
  • A case or entity with another entity stacked right on top of it have its connections removed (because you cannot walk onto it since you cannot go through the entity stacked right over it). A node without any connections is a pointless as no node on the graph in the computation of A*, so you can keep it alive (and possibly reconnect it later).
  • ... (Depending on your game rules, you may wish to alter this interface, like adding weight on edges, ... )

Now, all you have to do is to implement A*, but not by following regular 2D or 3D neighbours to travel, but by following connections (a.k.a edges). Two nodes are neighbours if and only if they are connected. You may wish to learn how to do A* on a general graph structure.

I would prefer to reuse the data structure you already have. So basically a 2D grid that is the floor with a bunch of entities that put over it.

A* actually works over a graph, so the trick is to make a decent abstract programming interface (API) for a graph. 2D or 3D grid A* is a trick by implicitly converting a grid into a graph with the shape of a lattice graph, where the nodes correspond to cases and where the edges connect neighbouring cases.

In this graph,

  • Each case of the floor is a node, connected to its four neighbours "by default".
  • Each entity/object is a node, connected to neighbour entities provided they have sufficient height so a character can walk across.
  • A case or entity with another entity stacked right on top of it have its connections removed (because you cannot walk onto it since you cannot go through the entity stacked right over it).
  • ... (Depending on your game rules, you may wish to alter this interface, like adding weight on edges, ... )

Now, all you have to do is to implement A*, but not by following regular 2D or 3D neighbours to travel, but by following connections (a.k.a edges). Two nodes are neighbours if and only if they are connected. You may wish to learn how to do A* on a general graph structure.

I would prefer to reuse the data structure you already have. So basically a 2D grid that is the floor with a bunch of entities that are put over it.

A* actually works over a graph, so the trick is to make a decent abstract programming interface (API) for a graph. 2D or 3D grid A* is a trick by implicitly converting a grid into a graph with the shape of a lattice graph, where the nodes correspond to the cases of the grid and where the edges connect neighbouring cases of that grid.

In your modified graph,

  • Like a lattice graph, each case of the floor is a node, connected to its four neighbours "by default".
  • However, each entity/object is also a node, connected to neighbour entities provided they have sufficient height so a character can walk across.
  • A case or entity with another entity stacked right on top of it have its connections removed (because you cannot walk onto it since you cannot go through the entity stacked right over it). A node without any connections is a pointless as no node on the graph in the computation of A*, so you can keep it alive (and possibly reconnect it later).
  • ... (Depending on your game rules, you may wish to alter this interface, like adding weight on edges, ... )

Now, all you have to do is to implement A*, but not by following regular 2D or 3D neighbours to travel, but by following connections (a.k.a edges). Two nodes are neighbours if and only if they are connected. You may wish to learn how to do A* on a general graph structure.

1
source | link

I would prefer to reuse the data structure you already have. So basically a 2D grid that is the floor with a bunch of entities that put over it.

A* actually works over a graph, so the trick is to make a decent abstract programming interface (API) for a graph. 2D or 3D grid A* is a trick by implicitly converting a grid into a graph with the shape of a lattice graph, where the nodes correspond to cases and where the edges connect neighbouring cases.

In this graph,

  • Each case of the floor is a node, connected to its four neighbours "by default".
  • Each entity/object is a node, connected to neighbour entities provided they have sufficient height so a character can walk across.
  • A case or entity with another entity stacked right on top of it have its connections removed (because you cannot walk onto it since you cannot go through the entity stacked right over it).
  • ... (Depending on your game rules, you may wish to alter this interface, like adding weight on edges, ... )

Now, all you have to do is to implement A*, but not by following regular 2D or 3D neighbours to travel, but by following connections (a.k.a edges). Two nodes are neighbours if and only if they are connected. You may wish to learn how to do A* on a general graph structure.