Specification of a path finding algorithm

Question

Hello, I'm working on a tower defense game.

The whole game is designed on a grid :
- I can place towers on the grid, troups need to find a new path each time I place one.
- Troups follow a path tile by tile on the grid, from a starting tile to an end, with a minimal tile count.

I recently had the idea to place multiple starting tiles, and every time I place a tower, I need to update a path for each of the starting tiles, whose path needs to be with a minimal tile count.

Thing is, there are multiple possibilities for every paths to have a minimal tile count (up + down = down + up in tile count).

I am satisfied with the result but I'd be happier if I could minimize the total path "tile count" (bringing some paths together at some point makes the tile count decrease).

Is there any way to do this ?

I do not need an algorithm which finds THE minimal solution, a solution close to a minimal one is enough.

Have a nice day 👍

My current code :

https://code.sololearn.com/cmSCI3d2n8CJ/?ref=app

Answer 1

Use path finding algorithm A*, here some great codes to study, created by Lily Mea
https://code.sololearn.com/Whey0tmX2Z61/?ref=app
https://code.sololearn.com/WPSt2EU171Xe/?ref=app
https://code.sololearn.com/WQgmra7O6CQt/?ref=app

Answer 2

Hi, Arthur Le Floch !

But isn’t it a mathematical problem? Some kind of optimization problem?
Before you start coding, you have to know what to code.

At least you have to show us the alogithm you need code help with. To find the algorithm is another typ of problem, then code it and can be a project by its one. Or what do you think?

Answer 3

Hi, Arthur Le Floch !

Focus on the math problem. Put the game aside for a while. Towers, troops don’t solve your problem, it just make it more difficult to understand.

So you have 2D-grid of nodes, identified in the same way a matrix identifies its elements. The nodes are connected in a network of links, making it possible for entity’s to move around in the network.

Answer 4

Hi again, Arthur Le Floch !

Of what I understand, you want to find a route for a orgin - destination pair, that for a part of it’s route share the route with at least another orgin - destination pairs route, and where both routes form a shortes path for the two origin - destination pairs? Am I right?

Or do you want to create this path when you found it. Because this is a kind of a contradiction; the link must exist, otherwise you can’t find a shortest path between the nodes.

Do all adjacent nodes in the network have links between each other? If so: use an existing algorithm to find all routes with the shortes path for the different orgin - destination pairs, and compare their routes to each other, to see if they share some part of the routes together. If so, you found what you looking for.

Answer 5

Arthur Le Floch
python, game, pathfinders, A*...
interesting rabbithole 😁
how about this?

https://github.com/AaronHe7/pathfinder

Answer 6

Bob_Li same thing I said to Per Bratthammar, in my case the whole game is in a large grid. Gathering every possible shortest path associated to every starting point, I end up with a huge amount of paths to compare.

Answer 7

Arthur Le Floch

I’m not shure I understand all assumptions. Anyway, it must be a (generic) cost for you to add a new tile, that is the reason you don’t want add extra tils (you have to figure out the price for this yourself), and take this with you in the equation. If the cost of adding a new tail is very high, it becomes okey to take a longer path. You have to decide how you value the different thing you want to happen, so it makes a basis for decisions.

If you really want help you must leave a more clear specification on what you want and how it works now. Now persons who want to help have to guess.

Best way is to take out the part of your code that you want help with an link it here.

Answer 8

Bob_Li I don't think this is the right way to start pathfinding in this case...

At the start of the game, almost the entire grid has no obstacles

Also, I think I can't really place conditions to find the shortests paths...

Answer 9

The current code I have ?

I do not have any layout of code for the thing I want to do yet...

Answer 10

Alright, here it is :

https://code.sololearn.com/cmSCI3d2n8CJ/?ref=app

Answer 11

If I understood wel, every time you place a new tower you have to do two things.
1. To calculate the minimal path for the troops that are already on the grid, by calculating the path from their current position to the end position.
2. Calculate the new minimal paths from the start positions till the end for the incoming troops.

Number one is the optimal path since the troops continue their paths from the positions they had when a tower is added.
To minimise the tiles you need a pathfinding algorithm like A* or Dijkstra.

Answer 12

Black Winter not exactly, the way I made it doesn't require troops to findpath again when another tower is placed. I just look if their position is in one of the tiles of any new paths, otherwise they teleport to a new start point with boosted stats.

Answer 13

Calviղ that's kind of what I done so far, but there are multiple starting points. I made an adaptation of a findpath algorithm i knew, considering each tiles of the grid are at a distance of 1 from neighbor tiles.

Each of the starting points need a path on the grid to reach the end.
As well as finding a minimal tile count for each paths, I also want to minimize the number of tiles we go through for all of the paths.

Considering (3, 3) is the end.
If path A is (1, 3), (2, 3), (3, 3);
If path B is (1, 4), (2,4), (3, 4), (3, 3);
Path A and B are both optimized, but I want the algorithm to return something like :
Path A : (1, 3), (2, 3), (3, 3) (same) ;
Path B : (1, 4), (1, 3), (2, 3), (3, 3)
So the amount of different tiles is reduced.

Answer 14

Per Bratthammar You're right, kind of a math problem.

I could do an horrible algorithm to find a perfect set of paths, but considering I'm rendering the grid, it needs to be quite fast (that's why I said I don't want THE minimal solution, it would probably be way too slow).

I might have found an idea right now, maybe a bit weird, but I'll give it a go:
Setting up the first path, then creating kind of a gravity grid using vectors to point the nearest path tile.
Then I could findpath for the second start, choosing each time a tile following the vector (under some conditions), updating the grid again and so on.

The reason I asked this question was to know whether or not there's already an existing algorithm doing something close to this, or if I could adapt an existing one to do what i want.

Answer 15

Hi Per Bratthammar ,

Every nodes have links to up/left/south/right nodes.

Maybe I wasn't clear.

I don't need to bring back the paths with some code whenever they cross, I just let it as it is.

Also, I consider "paths" as a list of path, from a start to the end, for every starting tile.

The solution to compare every paths won't be great in my case, as it would take way too much time, because, for a simple path, there are so much possiblilities:
-"up, up, left, left"
-"up, left, up, left"
-"left, up, left, up"
-"left, left, up, up"
All have 4 tile count.

(Considering the dimensions of the grid I'm using, the amount of different paths grows quickly. Now considering multiple starts, I would need to cross every path with every others path associated with other starts to calculate the path tile count I want to minimize.)

I don't want to check at the end if one path cross another.

Let's say when a tile is part of one of the paths, this tile becomes bright : I want my PC to be as dark as possible.

Answer 16

Hi Bob_Li, yes, quite an interesting thing.

The problem is : A* returns the shortest path between a unique start and the end.

I already done something like this, and this is not what I need. I need an algorithm giving me a shortest path for every start to the end.

Considering only this, I can use a pathfinder as much as I have starting points. (Already done that)

Thing is, I want the algorithm to minimize the amount of different tiles that the different paths go through.

The algorithm I have right now find me paths similar to :
(Using S1 : start 1, S2 : start 2 and E : end)

S1------------¬
S2------------E

Now I want it to be able to find something like this

S1¬
S2------------E

So we have a minimal number of "-" or "¬" in the representation.

Am I clear or not ? 😕

Answer 17

so you want solution paths to overlap as much as possible, even if they are not necessarily the shortest path？
I would probably say you would have to compute all possible paths for each start point and find the common one among them. or if there is none, use the shortest.

Answer 18

Bob_Li Quite the contrary. Each path needs to be as short as possible, and I want it to overlap when it's "interesting".

My algorithm returns paths that just overlap sometimes by accident, but leads sometimes to the previous example with S1, S2 and E on the "dumb" path (first one).

Now considering start 3 and 4 as S3, S4 and the end E, if I have something like this :

S3-------E--------S4

I want it to remains the same, the paths from S3 and S4 are minimal.

Answer 19

that is a challenge indeed...
So the strategy would be collect a list of shortest paths(could be one or more) for each starting point, and choose the ones with the most overlap with other starting points if there are more than one path in the list...

Answer 20

maybe you're collecting ALL paths intead of the shortest ones?