To give you some insight here we have 4 different pathfinding systems; aircraft, vehicle, baggage and passengers. The passenger is by far the most demanding and the one we are constantly measuring and improving. We currently use multi-threading, however, have not looked into multiple core processing yet. This is a matter of continuously improving the pathfinder and this is also the main reason we decided to start small and gradually add larger aircrafts.
We are fairly confident that we will eventually be able to simulate passengers in thousands. We have many ideas and tricks how to make it much faster as we scale up. As in real life, most passengers will actually not be constantly moving around but instead sit and wait, queue, dine, shop etc., activates which do not require complex calculations. The map size does not really affect this as most pathfinding will take place within the terminal.
The map size does not really affect this as most pathfinding will take place within the terminal.
I however find the above statement really odd. Isnât the size of your terminal, number/size of runways, number/size of aircraft stands what impacts how large the airport can grow and how many passengers that the game needs to simulate?
Simcity for example really struggled with performance and their only way to ensure it ran smoothly was severely limiting the map size, while the reason that Cities Skylines could have so huge maps was that it had really smart and efficient ways to deal with performance & pathfinding. I think that it would be the same with an airport simulation, if you for example only can fit 1 runway on the map or 10 large aircraft stands it will be impossible to get the same number of passengers that a huge map where you can fit 6 runways and 100 large aircraft stand could reach.
The pathfinding complexity depends on the graph size and connectivity, not the actual size of the objects on the map.
For a typical airport (that is scaled similarly to real-world airports) the aircraft movements side will be much much physically larger, but at the same time be a fairly simple graph, as the taxiways are well defined and not very interconnected. The same pretty much holds for baggage and vehicles.
Pathfinding for a passenger on the other hand actually involves more possible destinations and routes on a more complicated graph, so I can easily see that being the limiting factor.
So in that sense yes, the map size does not affect the actual performance-limiting pathfinding element. Optimizing the passenger pathfinding by clever use of idle passengers/cached paths/approximate solutions I could totally see leading to quite large airports being functional. (e.g. have cached paths to each location, but agents follow with a random spatial offset to give a natural look)
Could not have said it better myself. This is exactly my point. There is still a lot of testing and tweaking to do here as we scale up but one day there will be a trade-off between having fewer complex passengers vs. many with simple behaviour.
The pathfinding complexity depends on the graph size and connectivity, not the actual size of the objects on the map.
âŚ
Pathfinding for a passenger on the other hand actually involves more
possible destinations and routes on a more complicated graph, so I can
easily see that being the limiting factor.
So in that sense yes, the map size does not affect the actual performance-limiting pathfinding element.
My point is that a larger map (with same size objects) indirectly allows for the number of passengers which need pathfinding, the number of destinations as well as the size of terminal(s) to explode out of control.
Compare the following two examplesâŚ
Example A, Small regional Airport with:
5 Small aircraft averaging 50 passengers each, 5 Aircraft stands
Example B, Large International Airport with:
50 large aircraft averaging 250 passengers each, 50 large aircraft stands spread out over the large map in 3 different terminals.
In Example B the game is going to have to handle path-finding for 5x10 = 50 times more passengers, the number of possible destinations to check will also be 50 times as many ( since we need 50 times more capacity everywhere ), and the complexity of graph and size of terminal to check for paths and obstacles for each passenger will be at least 10 times as big ( probably more since the terminals need to be spread out to make room for aircraft stands ).
This means we are looking at a very roughly estimated performance hit of 505010 = 25â000 times worse performance.
I do agree that size of objects or map donât directly influence the path-finding performance impact, but indirectly it greatly impacts performance, or rather the other way around performance impacts how big map you can allow.
The amount of pathfinding doesnât increase exponentially, since passengers will be âconfinedâ to their terminal, and any traversal between terminals will be done via a select number of routes (since they canât walk across the tarmac).
So, yes, pathfinding cost will increase, but linear.
The pathfinding of the aircraft is negligable, since their routes are defined and few, and most of the time they are idle, unloading or loading passengers.
This means the player can increase the map size to what his/her computer can handle
The amount of pathfinding doesnât increase exponentially, since
passengers will be âconfinedâ to their terminal, and any traversal
between terminals will be done via a select number of routes (since they
canât walk across the tarmac).
This assumes that the size of terminals is always constant which is not true.
In my example each of the 3 terminals in the international airport needs to handle 17 times more passengers then the single terminal does in the regional airport.
This means even with your suggested optimization instead of 505010 = 25000 times worse we get something like 17173*3 = 2600 times worse performance estimate. ( linear would be 50 times worse âonlyâ )
Another assumption made here is that passengers never will need to switch terminal, which is not true either if the game is to have connecting passengers, or terminals which can only be reached by going through other terminals ( Both common things in larger real airports ).
This means even with your suggested optimization instead of 505010 = 25000 times worse we get something like 17173*3 = 2600 times worse performance estimate. ( linear would be 50 times worse âonlyâ )
True, it wonât really be linear, but 2600 times is still a whole lot better than 25000
Another assumption made here is that passengers never will need to switch terminal, which is not true either if the game is to have connecting passengers, or terminals which can only be reached by going through other terminals ( Both common things in larger real airports
I said that any passengers having to move between terminals will be through few, well defined routes. So pathfinding will go => Terminal A start => Terminal A - B hallway Entry => Terminal A - B hallway exit => Terminal B destination.
In other words, it will only have to path to the hallway entry, and from the hallway exit to its destination.
Itâs not perfect, but it does mean as i said, that cost wonât rise exponentially
Most pathfinding will be cached anyways, only having to refresh (part of) the cache when something changes, like an object / wall added or removed
True, it wonât really be linear, but 2600 times is still a whole lot better than 25000
It is, but I still donât see how you can get such an impact to work in decent fps without as Fredrik wrote extremely simple behavior and other trade-offs in place. Limiting the size of the map ( thus indirectly limiting traffic possible through fewer runways/aircraft stands ) is as far as I can see the only way to control how high traffic airports and how large terminals players can make.
I said that any passengers having to move between terminals will be through few, well defined routes.
How can you know that players will design their airports to only have single/narrow pathways between terminals though? Is there any way to enforce this?
Most pathfinding will be cached anyways, only having to refresh (part
of) the cache when something changes, like an object / wall added or
removed
Loadbalancing queues is a practical example that I think would be pretty hard to pre-cache, since if passengers is to learn which queue is the shortest and distribute evenly when there are say 40 queues through security all passengers passing security needs to check all of the queues. It depends how complex you want to make it ofcourse.
How can you know that players will design their airports to only have single/narrow pathways between terminals though? Is there any way to enforce this?
Well, they arenât allowed to walk outside, since that is restricted space, so it has to be walkways, mostly underground even (otherwise the planes wouldnât be able to pass).
Loadbalancing queues is a practical example that I think would be pretty hard to pre-cache, since if passengers is to learn which queue is the shortest and distribute evenly when there are say 40 queues through security all passengers passing security needs to check all of the queues. It depends how complex you want to make it ofcourse.
I donât have all the answers of course, but i can imagine that the pathfinding up to the security zone is cached, so only the last few tiles / picking the right queue has to be determined.
In the end, weâll just have to wait and see I donât think it really adds much to keep discussing this until we get our hands on the game
Ah yeah, I agree with that. I donât think the scaling is quite so bad, as the increase in number of possible destinations can be compensated by cached paths, and most of the time a passenger will be choosing among cached paths to a gate/bathroom/cafe/exit.
Even loadbalancing queues could be cached in terms of pathfinding; a passenger decides based on queue length which path to take to a queue, but doesnât dynamically compute the path. One could boil everything down to passengers only making decisions among possible destinations and using cached paths.
For large airports I can see vector fields being a great way to optimise traffic flow, though for smaller airfields and especially for craft/vehicle manoeuvres it might be best to work on an object by object basis as they donât need to work out their velocity to everywhere since they can only go on distinct pathsâŚ
Dont get your hopes up. Dont forget frontier had a whole team. Aoapsis is 2 guys
Although it would be great if they could pull it off, they said they used a*
Yeah, A* is definitely easier, thatâs just an example of how getting agents to follow paths is not necessarily a case of each agent always computing a new path.
