I’ve read you have some performance problems with pathfinding, i don’t know if you already implemented such feature or you are planning to… but here my ideas:
for Aircraft:
Add One-Way taxi, it’ll improve speed since some paths won’t be calculated.
Calculate the new paths only when taxi ways are edited, so that the plane already knows which path take before it lands.
for Humans (MORE IMPORTANT):
Add invisible ways (maybe shown in game with a filter or signals), those invisible ways are calculated only when one of the following events meet:
added or edited infrastructures
added a flight on the flight planner
So, when even thousands on guests arrive, you don’t have to calculate a real path “step by step”, but, if the guest need to go to the bathroom, there is already a path “dot to dot”, example:
Guest needs to do the following
bathroom
check in
security
food
rest
boarding
it starts from bus arrival A
the game already knows that the nearest bathroom is bathroom B (already calculated when the bathroom has been built and activated)
no need to calculate pathfinding, there is already one… the guest take it.
path from bathroom B to chek in F, same thing
and so on.
another thing to calculate before hand is timing, every calculated path should have an expected time…
so that the guest already know how much time take to reach boarding…
again, i don’t know if the game already works like this, but a way to improve more, would be to add the “sign” structure, and let the gamer create those paths…
other things could be “one way doors” and doors that can be blocked on command.
Some good ideas there, the “One way taxi-way” is a definite must. And signs! What is an airport without signs. Passengers need to know were the gates are, were rest rooms are located, and were they can get information. At the moment, passengers seem to know exactly where everything is.
I can shed some lights on our thoughts here. For aircraft, vehicles and baggage, standard A* path finding is sufficient as we are only talking about a couple of hundreds nodes at max. Of course, it can probably be improved by a a few 0.1 ms but not sure if it is worth spending time on right now.
For persons it is a different story. The path finding graph is quite big and a single paths may require thousands of nodes to calculate. Now, pre-caching all possible paths on the map is something we have considered but we are not sure this is fully scalable and suitable for ACEO. You will need thousands of paths from each interaction object (bathroom, gates, security, seating, shops, bus stops etc). It can scale massively on larger worlds and I would suspect it would take quite long time before the pre-calculated grid can be used efficiently (if it is being calculated in the background). However, we are currently experimenting with a new path finding system that is partly based on pre-calculating up to 90% of the paths. Initial performance tests looks really good and we hope that this will solve the current limitations the system has.
If you would pre-cache paths, do it room by room (or area) over time.
So, when a person has walked a path in a room, safe it as a path in that room.
Over time more and more paths will be available by default for the algorithm from cache.
To make this work; make a multi-node level path-finding; do not create a complete path, but a path in 2 layers, between area’s and within them. Have 2 queues going, first make an area to area queue (A1,A262,A2,A6,etc) and then stash that queue and add inside are paths the moment the person enters the area.
So, the second queue can read all precached paths in one area, what shrinks the depository that has to be scanned for possible paths lots smaller since it is cached per room. Only have the “in area” queue calculate new paths If routes to new objects are requested or paths are found blocked by the actors on an active path;
You could even have the game “auto-create” extra area blocks in large spaces on its own.
The raw (long) / specific (short) separation is used for several warehousing automated operation systems; the first layer will request resources on the work-floor in advance (cranes, vehicles, operators) and the second layer will only operate when the process catches up with the simulated expectancy of the forecast. When acting live, the system can even request extra resources if it sees problem in the mid-long forcats. The OS even allows to enter maintenance schedules and ‘mean time between failures’ of requested resources.
Great minds think alike! HPA* has been the plan since a few months back but we have not really had time to start implement it, now we finally feel we have the time. I can reveal that the basics are in place in a test world so hopefully we can roll it out soon.
Pleeeeaaaaaaase can we have one way doors!