Pathfinding algorithm

1
votes

I'm doing a project where the objective is to find the less turn-cost way to send X ants from point A to point B with the restriction that only one ant at a time can stand on "in-between platforms" - don't know how to say that in English - with the exception of point A and B.

I've already looked to algorithms such as A* or the Dijkstra's but they only focus on the shortest path to get from point A to point B which, in some cases, isn't the best as you'd rather take 2 longer path and send more ants in one turn.

And this is where I'm needing you. Do you guys know such an algorithm ?

Hope I'm being clear with my question and will be looking forward to an answers. Thanks.

EDIT : Here is an example of where the A* is not going to work :

-L-M-N-O-P-S-T-U-V-W-X-Y-Z--|    Going from one letter
|                  |        |    to another costs 1 turn
H-----I-----J------K        |
|                  |        |
START--A-B-C-D-E-F-G-------END

If I have 17 ants, the best option available is sending 2 ants at a time in directions :

  • START-H-I-J-K-W-X-Y-Z-END
  • START-A-B-C-D-E-F-G-END

rather than all in START-H-I-J-K-G-END as A* would suggest as best option.

2
path-findinga-star
I voted to close this because as the question stands you're 'shopping' for a solution. If you post the A* example and explain what the issue is with it, then that makes a more specific, SO-valid, question. Suggest you add the a-star tag too. - martin clayton
Well I'm only willing too enlarge my knowledge in path-findings - pelarejo

2 Answers

0
votes

you can use A* to solve your problem you just need to adjust dynamically your map to take the position of your ants into account

0
votes

You could use floodfill. What floodfill does is it traces every possible pathway and determines the best solution, but you get to define "best". For example, you can create a total time variable that tracks the time through recursion. You can make a recursive method that only returns the time variable when it reaches B, and then select the shortest value.