Home Game Development path discovering – Tile Based A* Pathfinding, however with a bomb

path discovering – Tile Based A* Pathfinding, however with a bomb

0
path discovering – Tile Based A* Pathfinding, however with a bomb

[ad_1]

The typical strategy right here could be to deal with your remaining bomb rely as a further dimension within the pathfinding house.

So given this example

2      ↑
   ──────┐
1   ←  o │ →
         │
0      ↓ 

    0  1   2

Our tile on the o (1, 1, 4 bombs) has the next reachable neighbours within the cardinal instructions:

transfer x y bombs price
0 1 4 1 step
1 0 4 1 step
2 1 3 1 step + 1 bomb
1 2 3 1 step + 1 bomb

This solves the issue of “closed nodes” interfering with attainable paths, as a result of the node you attain by blasting via the wall to the appropriate (2, 1, 3 bombs) is totally different from the node you attain by strolling down previous the tip of the wall, then proper, then up (2, 1, 4 bombs). So marking one as closed does not stop exploration of the opposite.

To be sure you can nonetheless terminate the algorithm, you rely each node on the exit tile as a aim node, whatever the variety of bombs left – so a path may be thought-about full whether or not it used no bombs or all 4. A*’s price minimization will select the most effective one in response to the parameters you give it.

You can modify your price perform to determine whether or not the algorithm ought to all the time discover the shortest variety of steps even when it has to make use of all of the bombs (bomb price = 0), or give it some trade-off like “use a bomb if it saves greater than 3 steps” (bomb price = 2 x step price, since a bomb use all the time comes with one step too)

When your maps or variety of dimensions are giant, you’d most likely need to assemble these tiles solely as-needed, moderately than reserving an array for each conceivable configuration (of which many won’t ever be used). For the case you describe although, an exhaustive assortment would not be an issue.

[ad_2]

LEAVE A REPLY

Please enter your comment!
Please enter your name here