search

jsettlers / settlers-remake

A Remake of "The Settlers III" for Windows, Linux, Mac and Android
http://www.settlers-android-clone.com
MIT License
354 stars 100 forks source link

Pathfinder: Settlers create jams as they try to go by one route #764

Open PaweX opened 5 years ago

PaweX commented 5 years ago

This issue was mentioned here: #309 (point 2). After a while of playing, the problem becomes very annoying. The settlers (especially soldiers) don't find another route if one is already busy. I was thinking about it a lot (I was also considering using a route manager). The best solution I saw is in The Settlers IV which doesn't have this problem anymore, at least in not such big degree. 8-AI-traffic_jams

homoroselaps commented 5 years ago

Hej @PaweX , I'm started working on this issue quite some time ago here: #563 #485 . I freezed further implementation because of scope explosion and time restrictions. I have some ideas as well how this issue could be solved. I havn't played Settlers IV much and so I'd be very much interested hearing about yours. Are you on the discord channel? Maybe we could even have a VoIP about that topicy.

PaweX commented 5 years ago

Unfortunately I am not on Discord, at least not yet. I will check again #563 #485, but more carefully. I will also do some tests in the Settlers 4, so I can provide more info. However my ideas are limited to design only (I can share them here), I didn't write any code. The Settlers 4 uses solutions from S3, however the developers fixed some of the common issues from S3 which we face now.

PaweX commented 4 years ago

In Settlers IV, settlers who come from opposite directions somehow go through each other, there is a little animation of passing through.

Unfortunately the time is so busy that I can't find any free one for programming and for settlers. Hopefully these tips will help a bit. Please check and see S4, even demo, because there is lots of solutions for these issues. These issues nearly don't exist there.

PaweX commented 4 years ago

A little idea that I was thinking about recently. What if we treat a settler (also warrior and specialist), who has a task "move to" and is standing, like a temporary barrier? So the algorithm will find another shortest route avoiding this "barrier" - if possible. If not possible then we use the first route.

I was also thinking about this: when the algorithm is finding a new route, it registers it and if there is too many units using this route (or some waypoints on this route) the algorithm is advised to find another route.

Also I would like to add that in S3 and S4 settlers don't go by one route (e.g. soldiers) - they split and some find alternative routes that are similar. If we have a group of soldiers, they don't go to one point but to area so they can't go one route as each soldier of the group has a bit different destination. It's not like that in JSettlers.

Settlers 3 - group of soldiers go to selected point: Soldiers don't go by one route: obraz Soldiers don't go to the same position: obraz

A little drawing to show what I mean (I didn't make it very accurate): Also, S3 units avoid busy routes obraz