algorithm – In a tile primarily based sport, with models that may transfer a certain quantity per flip, how do i make my pathfinding keep away from harm until it’s the solely legitimate path?

It seems like your sport is turn-based, so there might be a motion section the place you get to make use of up a sure variety of motion factors or transfer a sure variety of tiles. And it seems like for the motion section you do not care what number of “motion factors” or such can be utilized, simply whether or not you will get there or not.

A special case can be in the event you had one thing like ‘motion factors’ the place you would possibly need to spend some on motion and retain some to carry out an motion like attacking. That may make it extra difficult.

So what you need is a listing of all out there tiles you’ll be able to go to and the least harm you’ll be able to take whereas getting there. I believe every tile in your path then wants an array of objects with distance and harm, and you may’t merely mark a tile as ‘visited’, however examine if the brand new method you get there provides you much less distance, or much less distance for a given harm worth. Each paths ought to be evaluated.

So if you end up checking tilesTo and the tile would not exist, add it. If it already exists, add path to an array of from paths together with the gap. An instance, say you’re on tile B making an attempt to get to E, with the numbers representing the heights, and you’re taking 10 factors of harm for every degree dropped above the primary, and tiles are joined horizontally and vertically:

ABCDE
FGHIJ
KLMNO
PQRST

Peak map:

24100
23200
12100
01000

You start with a beginning node:

{ tile: B, from: START, distance: 0, harm: 0 }

Then you definitely have a look at the tiles you will get to and add paths to them, queueing for processing:

{ tile: A, from: B, distance: 1, harm: 10 }
{ tile: C, from: B, distance: 1, harm: 20 }
{ tile: G, from: B, distance: 1, harm: 0 }

The tile A node above generates just one new path to F if you cannot climb again to B, carrying alongside the ten harm from the earlier file, which is added to your record and queued:

{ tile: F, from: A, distance: 2, harm: 10 }

The tile C node once you course of it generates two new data (assuming you’ll be able to’t climb again to B) primarily based on the gap 1 and harm 20, including 1 extra distance however no extra harm. These are added to your outcomes and queued for processing.

{ tile: D, from: C, distance: 2, harm: 20 }
{ tile: H, from: C, distance: 2, harm: 20 }

Then you definitely add the 4 paths you will get to from G. However right here you’ll be able to examine the prevailing nodes and both change them or ignore your present path whether it is worse/equal in each distance and harm:

{ tile: B, from: G, distance: 2, harm: 0 } // ignored
{ tile: F, from: G, distance: 2, harm: 0 } // replaces and queues
{ tile: H, from: G, distance: 2, harm: 0 } // replaces and queues
{ tile: L, from: G, distance: 2, harm: 0 } // provides and queues

So for brand new nodes you generate, examine present nodes for that tile:

1. If an node already exists for a similar tile the place the harm and distance are each <= the brand new node’s harm and distance, ignore the brand new node – STOP
2. Take away present nodes for a similar tile which have >= each harm and >= distance of the brand new node. As a result of we ignored the brand new node and stopped at step 1 in the event that they had been each equal, both distance or harm might be higher than our new node and the opposite worth be higher or equal, so the brand new node is best indirectly and at the very least pretty much as good within the different.
3. Add the brand new node and queue it for additional processing

When including the node to tile B, we see that there’s an present node with harm 0 and distance 0. Since there’s an present node with the identical or decrease harm and the identical or decrease distance, we ignore our new node, we do not add it and do not queue it for processing.

When including the node for tile F, we see an present node with the identical or larger distance and extra harm, so we take away that present node, then add our new node and queue the brand new node for extra processing.

When including the node for tile H, there’s an present node from C with distance 2 and harm 20, so we change it with our new one as a result of it has decrease harm and queue the brand new node.

When including the node for tile L, there is no such thing as a present node for tile L so we add it and queue the brand new node. Our record now seems to be like this (feedback on queued nodes)

{ tile: B, from: begin, distance: 0, harm: 0 }
{ tile: A, from: B, distance: 1, harm: 10 }
{ tile: C, from: B, distance: 1, harm: 20 }
{ tile: G, from: B, distance: 1, harm: 0 }
{ tile: D, from: C, distance: 2, harm: 20 }// in queue
{ tile: F, from: G, distance: 2, harm: 0 } // in queue
{ tile: H, from: G, distance: 2, harm: 0 } // in queue
{ tile: L, from: G, distance: 2, harm: 0 } // in queue

That was the primary distinction, we are able to change present nodes solely distance or harm is lower than any present nodes for that tile and the opposite worth is identical or lower than the prevailing tile. However you’ll be able to have a number of nodes for tiles as nicely if one worth is larger however the different is decrease. Within the queue we are going to generate a brand new node for C from H that may have the next distance than the prevailing node, however a decrease harm. So we are going to queue it and preserve each.

{ tile: C, from: H, distance: 3, harm: 0 }

Each of these nodes will generate nodes for tile D by carrying over the harm and including 1 to the gap:

{ tile: D, from: C, distance: 2, harm: 20 }
{ tile: D, from: C, distance: 4, harm: 0 }

Say you may have a most motion of 4, so on this case you wouldn’t queue up the final node as a result of the gap is already 4, however the first node can be within the queue and help you transfer on to tile E:

{ tile: E, from: D, distance: 3, harm: 20 }

If you happen to had been utilizing motion factors, you would possibly need to current each choices for shifting to tile D to your participant. Both they will transfer there utilizing 2 factors and taking 20 harm however have 2 motion factors remaining, or use all 4 motion factors to maneuver there and take no harm.

In your sport I believe you’ll need to condense the record to have just one entry per tile with the minimal harm, so you’ll preserve the tile D node with distance 4 and harm 0. It looks like on your show you’ll simply present it as inexperienced or one thing since you will not be taking harm, however the E tile will present as pink as a result of the one solution to get that far is to take harm.