Pathfinding algorithm

Question

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.

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
– martin clayton, Commented Apr 3, 2013 at 13:45
Well I'm only willing too enlarge my knowledge in path-findings — pelarejo
– pelarejo, Commented Apr 3, 2013 at 13:59

tiridactil · Accepted Answer · 2013-04-03 13:35:27Z

0

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

answered Apr 3, 2013 at 13:35

tiridactil

3891 silver badge11 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

pelarejo Over a year ago

Yes I thought of that before but I've got an example where A* would go wrong. I'm gonna post it.

Morgan Hill · Accepted Answer · 2016-10-23 19:56:08Z

0

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.

answered Oct 23, 2016 at 19:56

Morgan Hill

764 bronze badges

Collectives™ on Stack Overflow

Pathfinding algorithm

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related