Using pathfinding

[Stalzak]

Hi y'all!

I'm trying to adapt a board game in which players can move a certain number of cases depending on dice rolls, but for now on paper i'm stumped by how i could program a function that'd check possible paths. I know next to nothing on pathfinding algorithms, so i figured you might have ideas regarding what i could use here and how to implement it. I want to be able to both show the player where a dice roll could take them (with a D4 for instance) and the different spaces they can land on once the roll is done, while taking into account dynamic obstacles and path limitations. I've heard about A* algorithms, but i'm not sure it'd really be the best suited here (sounds a tad overkill too doesn't it?)

Thanks for the help!

[quietmint]

With little information to go on and not being sure how complex the paths/movement rules are, can you represent each path as a linked link? The first element in the list is the first movement from the player's current space, the second element in the list is the next movement from that space, and so on...

Imagine a function that produces an array of of arrays with all these possible linked lists, given the player's current position and the number of moves. It shows the player can move to #6 in 1 move, can move to #1 or #2 in 2 moves, etc. This can be implemented with nested loops. Once you have this, you could now take the unique end values to show all the spaces the user could end the turn on (#4, #5, or #3) by making exactly 4 movements.

Code: Select all

$possiblePaths = [
  [ 6, 1, 3, 4 ],
  [ 6, 1, 2, 4 ],
  [ 6, 1, 3, 5 ],
  [ 6, 2, 4, 3 ],
  ...
];

[Tisaac]

If the paths is not too long, a good old while loop with a queue/stack should do the job.

[RicardoRix]

for each space, let's call it a node. a node class.

Each node could have a list of other nodes it can get to in 1 move. Now you can move from one to the other.
You can to go through all the different possibilities, building up a list of paths, essentially a list of a list of nodes.
Remember perhaps to potentially NOT go back on yourself (unless that's in the rules).
Your obstacles would know which nodes they relate to, or the node contains this information.

Depending on how dynamic the map/board is, any static array that's pre-calculated is going to help you out. You may even make use of this client-side too.

/this looks very much the same as quietmints solution.

[Stalzak]

I suppose i could try each way one by one sequentially! But since a player can move up to 30 cases, i'm unsure as to whether or not this would be the best idea efficiency-wise. And regarding nodes, some parts of the board will use them for sure, but given how there can be about 500 cases per board, i was hoping i could save myself some trouble :')
As for the info, give me a sec i'll try and explain the movement rules here to give y'all an idea

This is a race game, and there's two sets of fairly simple movement rules, one for straight lines and one for corners.

Straight lines: you can go forward or switch lanes, as long as you don't get back to a visited lane without overtaking another car.
Corners: imposed directions, you can only go to pre-determined cases. (which is where i felt like using nodes in the first place)

So as to not overcode, i was initially thinking about using cases' ids in straight lines to calculate distances, but if i want to take obstacles and lane switchings into account that's not gonna be an option i'm afraid. Also the number of lanes is not fixed so there's that.

I feel like once inside a corner, i could very well try each path sequentially as the possibilities will be fairly limited, but as for the straights i'm more unsure since lane switching with overtakings could easily modify the number of cases greatly. What do you think?

[quietmint]

The requirement to overtake a car before returning to the same lane complicates things, but it limits the number of possible moves, does not increase it.

The nested loop approach still works here. Basically, just build each possible path one step at a time. You will need to track the visited lanes as you build each possible path. As you compute the next step, check the overtake condition and visited lanes for this specific path so far, then do not include those moves if the condition isn't met ("continue" to the next iteration of the loop).

---

Does the user move the car step by step, one space at a time on their own? In that case, possible paths are not needed. You can just compute which step is allowed NEXT (e.g., all possible "paths" with distance = 1). Then move the car to one of these spaces and repat, giving the user another set of choices, until their movement amount is 0.

[Lymon Flowers]

I feel like once inside a corner, i could very well try each path sequentially as the possibilities will be fairly limited, but as for the straights i'm more unsure since lane switching with overtakings could easily modify the number of cases greatly. What do you think?

Are you going to adapt Formula D? If so, that is great news!

I had the same issue than you in Downforce. Basically, I went for the ID approach: every space has an ID. Every track is a PHP module with an array of spaces, each having coordinates to be put on map, an angle for the car token on this and a list of "next spaces". There are additional things like constraints needed by some maps.

In order to maintain the track easily, I made a SVG file for each, where I put SVG lines, each having a corresponding ID with the track. And a PHP script that iterates through maps and SVG files in order to put the right coordinates, which you do not want to maintain by hand.

Regarding the path finding, I went for the recursive approach because I am a Lisp guy, but the iterative would just work as well. You can check out the code for Downforce to have an idea. Note that the path finding code became a bit complicated because there are MANY imbricated movement rules and special cases in Downforce. Formula D would be simpler.

Benj

[Stalzak]

The requirement to overtake a car before returning to the same lane complicates things, but it limits the number of possible moves, does not increase it.
The nested loop approach still works here. Basically, just build each possible path one step at a time. You will need to track the visited lanes as you build each possible path. As you compute the next step, check the overtake condition and visited lanes for this specific path so far, then do not include those moves if the condition isn't met ("continue" to the next iteration of the loop).

That's very true, thanks for your input! I think i'll try this method and see how it'll go

Does the user move the car step by step, one space at a time on their own? In that case, possible paths are not needed. You can just compute which step is allowed NEXT (e.g., all possible "paths" with distance = 1). Then move the car to one of these spaces and repat, giving the user another set of choices, until their movement amount is 0.

I intend to make it so the user could move their car case by case, but I feel like i should try and allow players to advance more than 1 case at a time if they so choose, i can't imagine it'd be fun for anyone to click on little cases 30 times in a row with server confirmation in between each step... But also i wanted to give a preview of cases depending on player's gear at the start of the turn, in which case i do need the pathfinding anyway

Are you going to adapt Formula D? If so, that is great news!

Oh good catch, i am! To be real your work on Downforce made me want to try and adapt this one, so thank you for that o/
I'll probably take a look at your code yeah, thanks a bunch

[Lymon Flowers]

Oh good catch, i am! To be real your work on Downforce made me want to try and adapt this one, so thank you for that o/
I'll probably take a look at your code yeah, thanks a bunch

I don't want to be annoying, but I went to the licensing page and have not seen Formula D. You got a go from the publisher or are in touch with them?

[Stalzak]

I am in touch with them yeah! I've called and mailed their headquarters, apparently they're in the process of trying to find who's managing the IP, i'll relay the info for the available licences list whenever i'll get more news