Pathfinding with destructible obstacles

4
votes

I'm currently planning a game, but I have a hard time figuring the path finding algorithm and I was wondering if a generous soul would be able to help me with that.

Here's the scenario, I need an algorithm that calculate if it would be better to walk around obstacle or destroy them. I gave a "difficulty" to each tile of my game. For exemple a basic tile is 1 and obstacle can be between 5-100.

Here is some exemples. I must move from Red Square to Blue square. If I put an obstacle on the way I should get something like this :

http://i.imgur.com/UwIQ0IG.jpg

Explanation : Left or Right path is only 3 difficulty and the obstacle is 5. So it's better to walk around.

Second example :

http://i.imgur.com/0is3in9.jpg

Explanation : The algorithm as 3 choice, break the obstacle or walk around by left or right because it's the same difficulty level.

Last example :

i.imgur.com/sw13exL.jpg

Explanation : The algorithm must be able to find a "weak spot" and be able to walk to it and destroy it.

I'll continue to work on it. Hope you can give me some guidance.

2
algorithmpath-finding
A*? – SáT
If you can supply a numeric difficulty weighting like this, it should be simple to find the easiest path. Dijkstra's graph search algorithm will find the shortest path easily, and at the cost of a little more implementation complexity, A* can do the same, slightly faster. (A* is basically Dijkstra's with a heuristic to find better choices sooner). – zstewart
The best intuitive explanation of A* which I've used is here: policyalmanac.org/games/aStarTutorial.htm – zstewart
There's gamedev.stackexchange.com, which might give you some game-specific suggestions. – Peter Cordes

2 Answers

2
votes

You can use Dijkstra's algorithm. To use the algorithm we'll define the following graph. Each square will be a node in the graph. Between two adjacent squares we'll define 2 directed edges. The weight of an edge will be the number written on the pointed node (e.g. for an edge (a,b) the weight will be the number written on square b).
Then, by running Dijkstra's algorithm on the graph defined above we'll get the shortest path.

2
votes

You can do this with a very minor variation (actually no variation at all, you just interpret differently what is an arc cost) of Dijkstra's algorithm.

Basically, you can reach the "inside" of the obstacled square at the cost of its destruction, so you have a graph where all nodes are connected to all their neighbours (i.e., the obstacle does not "disconnect" the intervening nodes).

So in this case, going from A to B,

1 1 A 1 1 1
1 1 1 1 1 1
2 5 5 5 2 1
1 1 B 1 1 1

the costs would be

2 1 A 1 2 3
3 2 1 2 3 4
5 7 6 7 5 5
6 7 B 7 6 6

and you would go straight downwards.