NewGRF (Air)ports - general discussion

[DaleStan]

And what if the plane moving left wanted to turn to its right (absolute direction: up) at the intersection?

[Aydan]

you got me there

[Alberth]

There are even worse scenario's w.r.t. routing at an airport. There may for example land another aircraft at any time, and start claiming piece of the route too.
After writing my previous mail, I did some more thinking, and I think I have cracked the first item. Under the assumption that each aircraft takes a fixed route, there are a number of routes 'active', that is, a plane may arrive at any one of them, and it should be able to find a route without getting in a deadlock with another aircraft. I think this can be solved by requiring that if between points A and B immediately next to each other, there is a route from A to B and vice versa, then A and B should belong to the same block (ie be claimed both at the same time). They should probably also be released together.
If the airport blocks fulfill this property, then there is only traffic in one direction between tow blocks.

That is however not enough, cycles should also be collapsed into one block. A cycle is the situation that an aircraft at A wants to go to B, an aircraft at B wants to go to C, and at C there is an aircraft that wants to go to A. The only way to prevent this (I think) is to merge A, B, and C together into one block. (cycles may also be larger, ie run over more than 3 blocks).

I think these two things are enough, at least for a static set of routes at the airport. The trouble is however that new routes become active and old route become non-active (eg when a plane enters a terminal, no other plane can go to that terminal. As soon as it leaves, these routes become active again).
The latter has the highly unpleasant feature that a plane going from a terminal to the hangar will at some point release the terminal and enable the route from the hangar to the terminal it just left, If both routes are the same, the entire path between the terminals and the hangar becomes one big block
(you can observe this at the smaller airports quite well).

In other words, we need a trick somewhere to prevent the entire airport from becoming one block (which obviously solves the collision problem, but is somewhat less efficient ).
I have to program this block calculation, so I can run a few experiments with it. (Unfortunately, not this weekend.)

[Aydan]

This idea just struck me:

The plane reserves the entire route it wants to travel and put's directional markers on the reserved tiles. The markers might be two four bit values designating entrance and exit point for the tile.
That means that other planes can't travel these tiles if they'd go against the reserved direction but could cross them or travel the same direction.
I think there's other hangups I haven't thought about with this system but that's for you to find out

Aydan

[Alberth]

I really like your idea. It very different from my ideas.
An aircraft travelling in the same direction may not be possible, since then you don't know when you can safely remove the bits for the direction (ie after the second plane, another one may come, you don't know).

I don't understand why you need so many bits for a position. From the NewGRF
airports description, it seems that I only have bits 0x40 to 0x7A (ie 64-5 = 59
bits). With 8 bits per position, we'd run out of bits very fast.

I thought about this yesterday on the way home, and came to the conclusion that
one bit is needed for recording an aircraft at the position (to prevent an
other aircraft bumping into it), and one bit for each direction that an
aircraft may go to (and the latter only if there is a possible deadlock).

One problem that your approach doesn't seem to solve is a cycle, except with
your idea, a cycle consists of three or more positions instead of blocks.
Not sure whether this is fixable.

Another thing that needs to be addressed is the ability of testing set bits.
The NewGRF airports docs seem to allow testing for unset bits, but not for set
bits.

DEVS: Is this true?
That may complicate matters.

With respect to NewGRF airports, I have a lot of questions about them. Maybe
someone can help me to explain a few things.
(note: Below are a few (I suspect) akward fundamental questions. Please don't
feel offended by them, my only intention is to clear up unclear points and/or
to expose weak points so we can work on improving them).

• Why there are bits for the helipads but not for the runways? In fact, can't these bits not be merged? The aircraft itself is already aiming for either HELI* or TAKEOF/LANDING, so this can be coded in the state machine.
• related: how does CHOOSERUNWAY work?, I don't seem to be able to specify a set of bits that it should check for availability of the runway.
• One step further, why does a hardcoded set of bits exist at all for terminals,
  and pads? I suspect that it comes from the desire to implement
  CHOOSE{TERM,HELIPADS}. However, that can also be coded in the state-machine as
  far as I can see, and it needs to be coded any-way in order to move the
  aircraft in the right direction.

I realize that letting go of these things makes coding the state machine more
difficult. (What I am kind of asking about is a more general and simpler
implementation (less hard-coded limits), and move the hard-coded limits of bits
towards guide-lines for an airport design.) Hence my final question. I kind of
expect that somebody has written a code generator that reads a human-readable
textual description of the state-machine, and outputs the bytes. Can I download
that somewhere?

Sincerely,
Albert

(and sorry if I asked stupid offending questions)

[Aydan]

The markers might be two four bit values designating entrance and exit point for the tile.

@Alberth: you are right about the amount of marker bits.
This should have read "The markers might be two two bit values " since you can only have four different entrance or exit points.

An aircraft travelling in the same direction may not be possible, since then you don't know when you can safely remove the bits for the direction (ie after the second plane, another one may come, you don't know).

You'd need a reference counter for that. Or maybe a reservation stack for each tile. This reservation stack would also allow planes to prereserve conflicting routes and wait their turn.

[DaleStan]

No, there are at least 8 possible entrance points. Don't forget the diagonals. But you don't have to track exit points; the only restriction is that planes can't exit where another plane has already reserved "enter".

[richk67]

I welcome any comments about airport scaling

OpenTTD is an abstract game, not a to-scale simulation. However, in theory you can design an airport for any size.

Finaly I would like to ask one question - I noticed, that it is not possible to code an airport with more than 256 tiles. You can build 16x16 or even 15x17, but as soon as you go over 256, game crashes. This is feature or bug?

If confirmed, its a bug. Can you send me the .grf or preferably a commented .nfo of the airport you were testing with. It is very easy to get your .nfo out of step, so I would double and triple check the 0E layout.

[richk67]

I really like your idea. It very different from my ideas.
An aircraft travelling in the same direction may not be possible, since then you don't know when you can safely remove the bits for the direction (ie after the second plane, another one may come, you don't know).

I don't understand why you need so many bits for a position. From the NewGRF
airports description, it seems that I only have bits 0x40 to 0x7A (ie 64-5 = 59
bits). With 8 bits per position, we'd run out of bits very fast.

I thought about this yesterday on the way home, and came to the conclusion that
one bit is needed for recording an aircraft at the position (to prevent an
other aircraft bumping into it), and one bit for each direction that an
aircraft may go to (and the latter only if there is a possible deadlock).

One problem that your approach doesn't seem to solve is a cycle, except with
your idea, a cycle consists of three or more positions instead of blocks.
Not sure whether this is fixable.

Im a bit lost following what you and Aydan are discussing. The features you want are all present already in the NewGRF Airports system. The whole block locking and release system can control the aircraft fine. If you are discussing a proposed modular airport system, then please start a new thread. At the moment I have little idea how/whether your discussion is even relevant to the NewGRF airports.

Another thing that needs to be addressed is the ability of testing set bits.
The NewGRF airports docs seem to allow testing for unset bits, but not for set
bits.

The doc doesnt define any of the manipulation procedures. If you look in the code, you will see a whole host of block manipulation functions in fsmblock.h & .cpp. These do everything from testing one bit, testing several, testing for clear, testing for clear if owned, set all, reset all, etc.

With respect to NewGRF airports, I have a lot of questions about them. Maybe
someone can help me to explain a few things.
(note: Below are a few (I suspect) akward fundamental questions. Please don't
feel offended by them, my only intention is to clear up unclear points and/or
to expose weak points so we can work on improving them).

• Why there are bits for the helipads but not for the runways? In fact, can't these bits not be merged? The aircraft itself is already aiming for either HELI* or TAKEOF/LANDING, so this can be coded in the state machine.

No runways since currently we do not explicitly use numbered runways. It is likely that runways will not be treated in any special way whatsoever. It is merely a sequence of positions & blocks. However, helipads must have an explicit reservation block so you can tell if a heli has reserved the helipad, but not yet reached it.

[*] related: how does CHOOSERUNWAY work?, I don't seem to be able to specify a set of bits that it should check for availability of the runway.

Currently it doesnt. The most likely way will be to be a minimum runway length, compared to the value held in the aircraft's spec. However, since that data is not yet in the aircraft spec, its all academic.

When implemented, my current idea is:
IF CHOOSERUNWAY_length > Aircraft_Min_Runway AND CAN_RESERVE(reserve_blocks) THEN GOTO new_pos ELSE continue

[*] One step further, why does a hardcoded set of bits exist at all for terminals,
and pads? I suspect that it comes from the desire to implement
CHOOSE{TERM,HELIPADS}. However, that can also be coded in the state-machine as
far as I can see, and it needs to be coded any-way in order to move the
aircraft in the right direction.[/list]

Yes, it makes choosing the terminal/helipad simpler.

I realize that letting go of these things makes coding the state machine more
difficult. (What I am kind of asking about is a more general and simpler
implementation (less hard-coded limits), and move the hard-coded limits of bits
towards guide-lines for an airport design.)

Once there is a demand for more than 36 terminals and 24 helipads on an airport, then it may be worth considering removing the limit and implementing a different way. However, other than stupid mega-ports that are totally impractical, I dont see that even 36/24 will be reached.
The most likely limit to be reached first will be the number of custom blocks (40h-7Ah). My Munich airport uses somewhere around 40 blocks, but it is about reaching the limit of sanity. I suspect the limit may be hit when I build Schiphol, but you can always save on blocks by having larger taxiing zones.

Hence my final question. I kind of
expect that somebody has written a code generator that reads a human-readable
textual description of the state-machine, and outputs the bytes. Can I download
that somewhere?

I have written a converter that takes the *correctly formatted* old style OTTD state machines and outputs them in .nfo. However, this is not a human-readable textual description / editor. As it only converts the old system, and that old system did not have a concept of release-blocks, then the output is at best a first pass.

I may write an editor in future, but if you keep your .nfo well commented, I find there is little need for dropping out of .nfo hex coding, since you will need to modify bits of it there anyway. One of the joys of .NFO ... NOT.

[Alberth]

You'd need a reference counter for that. Or maybe a reservation stack for each tile. This reservation stack would also allow planes to prereserve conflicting routes and wait their turn.

Nice suggestions, but the specs give you only 60+ bits, so I think these options are not exactly feasible...

Albert

[richk67]

I think you two have totally misunderstood how the spec and the aircraft controller actually work and interact.

When an aircraft's route is blocked because another has reserved the route, it waits for the route to clear (unless instructed to do something else). This is already coded, in and working. So, as far as I can see, the system already does the thing you are dreaming up some weird and complicated scheme for.

[Alberth]

Im a bit lost following what you and Aydan are discussing. The features you want are all present already in the NewGRF Airports system. The whole block locking and release system can control the aircraft fine. If you are discussing a proposed modular airport system, then please start a new thread. At the moment I have little idea how/whether your discussion is even relevant to the NewGRF airports.

The problem we are discussing is the generation of paths over an airport such that aircraft do not collide.

I was planning to create a new thread, but after yesterday's experiments, that won't be necessary..... See below

I realize that letting go of these things makes coding the state machine more
difficult. (What I am kind of asking about is a more general and simpler
implementation (less hard-coded limits), and move the hard-coded limits of bits
towards guide-lines for an airport design.)

Once there is a demand for more than 36 terminals and 24 helipads on an airport, then it may be worth considering removing the limit and implementing a different way. However, other than stupid mega-ports that are totally impractical, I dont see that even 36/24 will be reached.
The most likely limit to be reached first will be the number of custom blocks (40h-7Ah). My Munich airport uses somewhere around 40 blocks, but it is about reaching the limit of sanity. I suspect the limit may be hit when I build Schiphol, but you can always save on blocks by having larger taxiing zones.

My idea was that all bits are controlled by the state machine any way, so why hard-code allocations? Just give a set of bits, and let the airport designer allocate them in any way he likes.
In that way, he can only run out of bits rather than a particular kind of bits.

You may want to have some conventions though to guide the designer

I may write an editor in future, but if you keep your .nfo well commented, I find there is little need for dropping out of .nfo hex coding, since you will need to modify bits of it there anyway. One of the joys of .NFO ... NOT.

I was thinking about simple textual imput, like ('#' is a comment line):

Code: Select all

#         P2 -- T3
# HAN    / \                  L: landing
#    \  /   T2                F: flying holding pattern
#     P1         T1          Pn: intermediate-pos n
#       \       /           HAN: hangar
#        P3    P5            Tn: terminal n
#          \  /              ST: start take-off
#           P4 -- HET        ET: end take-off
#          /  \              SL: start landing
#        P6    P7 -- HL      EL: end landing
#        /       \           FT: flying take-off
# ST -- P8 ------ P9 -- ET  HET: heli end take-off
#  L                    EL   HL: heli landing

# end landing -> Terminal x
path types = plane,
     state = ENDLANDING, heading = TO_TERMINAL, new_state = TERMINAL,
     positions = EL(P7) P9(P7) P7 P4 P5 T1 ;

with a lot more 'path' thingies of course.

It is quite simple to parse this and generate a set of bytes (or the ASCII-HEX equivalent of it) from a description like this.



With respect to generating paths on an airport, I implemented my block computation algorithm, and it does what it is designed to do, except it is not enough
I entered the above city airport in my algorithm, and defined paths that should be travelled. Sure enough, it found collisions near the hangar, which were easily fixed by merging all those position into one block: "

Code: Select all

block P1P2P3P4 = P1 P2 P3 P4 ;

". It also found a deadlock situation around the runway, for example:

Code: Select all

bit P2: AC(heli)@P7, HELIENDLANDING, heading TO_TERMINAL, [P7 T3]
bit P6: AC(plane)@P4, HANGAR, heading TO_TAKEOFF, [P2 P3 P1 P4]
bit EL: AC(plane)@P6, HANGAR, heading TO_TAKEOFF, [P6]
bit P7: AC(plane)@P9, ENDLANDING, heading TO_TERMINAL, [EL T1 ET P8 P9 L ST]

this is a cycle of 4 aircraft (the "@XX" defines where the aircraft is, the bit at the front is what it needs to go further, and the bits listed at the end between square brackes are the positions owned).

I tried a few times to solve this problem. It appears that two solutions exist:

• make the entire airport 1 block (this is what the algorithm does)
• have a plane also claim P7 when landing. The rationale behind it is that having this position enables the new plane to get out of the way for outgoing planes. Also, it prevents more planes from landing. (I suspect this is what OpenTTD does, but I am not sure.)

I don't see how to make the algorithm generate the second solution (except when you have a rack of CPUs for computing this).
Getting the first solution is already a lot of work, my computer is running for a long time with several G memory usage, for a limited number of aircraft.

So it seems that even for a statically defined airport with statically defined paths, generating/verifying blocks to eliminate deadlocks is already nearly impossible, let alone for dynamic paths on a dynamic/modular airport. For me, this concludes the experiment. It is truly non-feasible, even outside the game (which I was hoping to get a solution for).

Maybe if I have central control on all airplanes (ie I decide what planes moves to where in what order), it would be feasible. Detection of entering a deadlock is much cheaper than generating a decentral (ie each aircraft by itself) state machine that has no deadlocks.

That option is however far outside NewGRF airports.

Albert

[richk67]

Ah, OK. I see.

The current NewGRF_ports aircraft controller is very effective at eliminating deadlocks, as long as you specify the whole route you require. It then tries to reserve the whole route, and only 1 aircraft is allowed to reserve any block. No aircraft can release blocks they do not own (so you can do "lazy" releases of too many blocks quite safely).

I recently coded up the SFO airport, and apart from a typo, there were no deadlocks first time. Doing this automatically though, may be nigh on impossible as you say.

[skidd13]

After a longer time of drawing abstinence I started to work on the sprites for the set again.
Here are a few ideas I'm on.

[athanasios]

Recolored roof is better. The raised is not so nice [EDIT: in proportions] but since we are going to need it for big aircraft I prefer it. Just use the recolored roof there too.

[richk67]

After a longer time of drawing abstinence I started to work on the sprites for the set again.
Here are a few ideas I'm on.

Raised hangar is much better. The old roof never bothered me, so I dont really have much of a view on it. Whatever you are happy with.

The Terminal Building X is very useful. The 4 Ls, and 4Ts would be really handy. It would also be great to have a skidd-style rotunda for parking 7 aircraft in the round (like at Gatwick) would be great.

My only other wishlist item would be a double width hangar. The Munich airport hangar covers two adjacent tiles (in the X axis SW-NE), and can have aircraft entering the upper side while another exits next to it. Pretty cool, but it looks a little naff as two separate hangars.

Great to see you back on this. I'll get MUC finished soon, and then hopefully try to get NewGRF Station animation working so we can have rotating radars again (ahem!). I could just say "its a planar array radar, and doesnt need to spin" but that would be a bit of a cop-out

[athanasios]

My only other wishlist item would be a double width hangar.

Now you are reading my mind richk67!
Actually I didn't say anything, expecting to be mentioned from you in due time, as this issue has been discussed before. May I get the licence and ask for a 4x4 hangar for future usage? Seems larger aircraft need bigger hangar.

[xmart2k]

i would like to give a suggestion on this one too. In real life most of the airport are outside the town, and you can get there using a bus, cab or other type of cars, in this case it would be nice that the airport to have a bus station incorporated(adding a bus station after you build the airport is not that "beautiful"). Probably this is a little to hard to code, but was just a suggestion.

[doghousedean]

you could just leave a space in the airport design to slot one in after building airport.

[richk67]

The system also allows you to leave holes in the layout, so it is possible to have an airport with a bus station inside, etc. My Schiphol design has one runway (the north western one) with a gap of 2 tiles before the next part of the runway. In real life, the motorway runs through this, and you can set it up just like that in NewGRF Airports.