Part 20 Navigating the cosmos

Graftgold Memories.

The Legend Of Avalon was one of my favourite games to develop. Andrew and I were firing on all cylinders and this was perhaps our most creative period.  I wanted to try something completely new. I had just read a book about Glastonbury and the Arthurian legends and thought this would be good subject matter for a game. I played Dungeons and Dragons sometimes and wanted to recreate the feeling of exploring a huge underground complex of rooms and tunnels with a 3d view. Nothing like this had ever been done, the nearest to what I wanted was Attic Attack which used a top down view. I experimented on paper with a side view. I drew scenes rather like a stage play. I cut out a frame and moved the scenes underneath to see what it looked like. I then adopted my Lunattack horizon routine to display the edges of a room. It was built in sections so I could easily have different room sizes. I knew I couldn't scroll too many graphics so decided to keep the background mostly dark with the suggestion of wall texture here and there. The illusion worked well. I then added the wizard. I modelled him in plastacine and sketched the model from 8 directions on squared paper then roughly shaded the squares. This was converted manually to hex codes and keyed in. As the graphic was large and needed 8 frames I could not afford walking animations so designed him cross legged so he could levitate around.  That is the secret of designing for limited resource. You have to make a feature from the limitation. 

I wanted a huge event based adventure that matched the complexity of text based adventures. I designed a central system that meant I could code the adventure very compactly.  I did this by having standard objects which were described by about 8 bytes for each state. 
Each object/state had:
Graphic Number : Thus could visibly change of the state changed.
Text Number:        A description of the current state
Movement pattern. So their behaviour could change per state
Event:   This was the event that the object  emitted in this state.
Trigger:  The event the object wanted in this state to change to the next sequential state
Flags:  Whether it could be picked up,moved, had gravity etc.

The event and trigger were the key elements. Each object emitted its event at its current location. The events/triggers were either specific events so a specific object could cause another object to change to its next state, or general events such as applies a force that can break things.  For the current room the objects put their events in a list. Some events were limited to a local X,Y position others were room sized. Each object also looked in the event list for its trigger and if it found it and the position matched it changed its state to the next state. That generic mechanism was all I needed for the whole adventure.  For example a mouse was in an invisible untakeable state until triggered by the cheese to appear,move and be takeable. It then emitted the trigger to change the state of an invisible key part.
I built up a huge chain of triggers/events to form the adventure plot. Also ai characters , magic, missiles etc all emitted events that could change things.

Dragontorc adventure object state data. 

Deepest Blue Progress.

I said that writing a game is like running a marathon. I have been at the point they call the wall where you wonder whether it is worth carrying on. Each step is painful  and no end is in sight. You just have to grit you teeth and keep going. I keep a diary and look at what I have accomplished over the last few months. That reassures me I am getting somewhere even though the "to do" list seems as long as ever.   Last month I did some important refactoring of the main structures to make the world data more manageable. Now it was time to get the AI using the new structures so ships could fly between sectors and systems.

To recap I had divided the galaxy into star systems.  This kept data segregated and meant that each could be run on a different server in the future. Systems were connected by warp paths.  Systems consist of a number of sectors designed to restrict the coordinate size of each space region to avoid huge floating point numbers that would be inaccurate. The sectors contained the space objects such as asteroids, bases ,ships and sector or system warp points.  So there is a three level network of nodes.
At the top level is a network of systems. Each is a network of sectors, each of which is a network of patrol points to navigate around a sector. This tiered design prevents networks having too many nodes. To navigate you need data about combinations of nodes which gets exponentially huge. With small networks you can devise simple look up tables to help things navigate.

"What is the next step to get from A to B?"
A tiered network had its own headaches. A warp point needed to know to which system/sector/locality it pointed. The game only creates systems as they are discovered so all of this is dynamic.  The key routines for the AI was a routine to supply the answer to the question, "what is the next step to get from A to B?". If A and B are in different systems the AI needed to  know what is the next system to go to, what is the next sector to get to this warp point, and what is the next local step to get to the sector warp point.  Each step of this needed coding as an AI program that could drive the ships around. As it was complicated I needed it to be generic so any kind of ship could just use it.

I had already designed the AI mechanism. An important feature of AI control is that it is an inverted program structure in Jackson speak. That is each cycle does a bit of the processing for each ship then the next cycle picks up from where it got to last cycle. Thus a ship's routine may have a structure such as
Loop thru Nodes
    Drive to Node.
    If close choose next node
end loop
The loop structure is inverted, that is it is spread over many game cycles rather than just running till it exits.  Ways of doing this are discussed in my programming tips.

I coded this with a state based process system. Each AI program through several states which can loop have conditional statements or call other AI programs. So a ship doing navigation to a new system can change to a fighting pattern to defend itself then resume its navigation when finished.

"The more I thought about it the harder it got"
As a diversion to all this background programming I thought I would add a gameplay element so I could see the game working again and tease out any issues that may have crept in. I had added asteroids and wanted a way you could play around with them so thought I would add a harpoon to grab them. Then you could tow them , collect small ones. Maybe the same mechanism could be used to grab ships or space junk. I wanted to have a go at inverse kinematics so thought I would have some kind of chain or arm with multiple joints. To make it easier I wanted them all the same size. I coded the basics of the new object except for the positioning. The more I thought about it the harder it got.
One end of the chain had to be fixed to the hull of the ship , the other either free or fixed to another object. The hard problem was when the chain was fixed and not taut. How do you work out the positions of all the links in the change? I looked up many web references  and quickly realised this was not a trivial subject. Most methods were too slow and cumbersome. I spent days sketching diagrams and struggling to understand the maths. In the end I implemented my own method after looking at the FABRIK method. That iterated back down the chain and then forward until it converged on a result or was abandoned. I improved on the design to give a much better guess at the orientation of each link so I could get a reasonable linked chain in once pass. Its working pretty well but glitching slightly as it changes from taut to slack modes. I will revisit this later as I want to make use of it first to check it is worth keeping. I tried capturing asteroids and for a while they were ok they suddenly catapulted off into space. It was all due to the maths of the reverse collision, when the chain pulls the asteroid.  I had forgotten that taking the dot product of the chains direction and the asteroids move lost the sign of the move and just says whether it is along the chains vector. Easily fixed you need to take the original move components multiplied by the dot product and remember to reverse them for the pull effect. I also added mass into the equation so the ship and asteroid are both affected, rather like a collision in reverse.

I added a mechanism to retract the chain to couple the asteroid to the ship. This was what I needed to pick up containers and transport them. So next  I coded a container object. I wanted these to be stackable and also linkable like a goods train so added special collision code to deal with this. The containers would assist in the shunting by acting as if they were magnetic and so align themselves as they were moved close together. I now need to work out a control mechanism so the ships can control grabbed objects. The chain will probably be a kind of robot arm similar to the space shuttles arm. I think I will try this out and if it is fun use the same code to allow the player to build things.

 Programming Tips.

I had a request to talk about programming AI routines. This is a huge subject , nowadays people use neural nets and other complicated devices. Remember that a game is an illusion and all we need to do is create the illusion of AI. I always remember a review of Paradroid saying how the messenger robots sped off to report the position of the player to the guard droids. This was all an illusion, they just ran away, but illustrates that if you make things act as though they are intelligent then the player reads a lot more into it.

It is still a daunting problem. How do you make something act as if it is intelligent. The way I do it is to think about the possible main actions an  Artificial Intelligent Character (AIC) can take. For most of the games I have developed these are surprisingly similar and fisrt surfaced in "Avalon".  The most basic of choices is attack or flee.  Stupid AIC's or clever ones that know they can beat you will usually attack. If they think they can be beaten they are not so keen and may stay their distance , retire or flee in blind panic. This can be simulated by coding several primitive actions and having a way of choosing between them.  Suggested primary actions are
Move Towards Player Recklessly.
Move Toward player slow and steady.
Maintain a distance to player ie shadow their moves.
Move at 90deg to player  ie dodge sideways
Move away from player in controlled fashion.
Move away from player recklessly
Move randomly.
Stop.
Do the same as last time

By changing how often you make the decision you can make things look nervous or steadfast.
An easy way of working these into a more complicated patterns is for each to have a set of probabilities of each primitive. This can be a simple set of descending numbers. Then you get a random number and compare it to the list in sequence until it is greater than the chance number.

These macro patterns can then be put in a table. You can index into the table using things like the relative strength, morale friendliness etc.


Another trick is to have predetermined sequences or patterns in a particular situation. Take for example a ship wanted to do a bomb run. First of all they keep their distance ,look for an opportunity then close to launch range, release their bombs the retire. The different components of this are again the primitives we discussed above with the addition of some kind of shall I attach decision which could be something like "am I behind player".


AI navigation of complex game scenes can take a lot of processing so is best done be adding things like waypoints or patrol paths. This was the method Paradroid used to give its effect of intelligent movement. In Ranarama and Bushido I used a game map that had special data on it. The player left arrows rather like footprints to tell the AIC go this way. There were also arrows pointing to the doorways so the AIC don't have to keep bumping into walls.   For a multi height game like Uridium a contour map could be used so the AIC fly at the correct height.

I like to add touches so AIC's react to the situation. In Avalon when high magic was used certain AIC's went into panic mode. I added a room fear variable so mass slaughter could cause AIC's to retreat or panic. I just added the room fear the  AIC own fear. The room fear gradually subsided.
Its the little touches that bring a game to life. Early meanies were usually really dumb and just had a set pattern. You only have to add some kind of a reaction to the players move to change this and it can be done quite simply without complex code. I usually add a bit of randomness so things are never totally predictable. It is good to have risk and surprise in games. That is one of the secrets of the playability of my games.