..O Deniz's personal pages
/home /about

Navigation order processing

December 17, 2017

Having ships is useless if you can’t boss them around the grid. So how would you do that, be also allowing multiple ships to move at any given time without running into each other? The first iteration of the path finder was the rasterized path finder I explained here. This method will provide a list of cells that the ship must travel through (I since have added a new algorithm that takes into account any obstacles in the way. It just returns a different list of cells which isn’t of any significance for the navigation command system). When the user clicks on a ship, we need to store that clicked cell and it’s ship into a temporary variable. The first click will also highlight the possible cells the ship can navigate to. The post about cells in range explains how there are calculated. The second time the user clicks on a cells, it can mean 3 things

  1. the user wants to navigate to a cell
  2. the user wants to cancel the selection
  3. the user wants to select another ship from his fleet
  4. the user wants to attack an enemy ship

We will address the first 3 items. Items 2 and 3 are simple so let’s get them out of the way first. If the user wants to cancel the selection, he just clicks on a cell not highlighted by the cells in range call. We just need to check if the clicked cell is in the list returned from this call. If not reset the variable that holds the clicked ship to return to the initial state. If the user wants to select another ship to move, if has clicked on a cell with one of his ships. Since he can’t attack that ship, just check if the clicked cell has a ship on it and if that ship belongs to the player. If true, set the selected cell to that one.

Here is an image of a state machine that shows to transitions and states

The red transition is cancelling the selection, and the green transition is selecting another ship to navigate.

Now let’s explore the case where the user wants to navigate to a cell. We need to support multiple ships wandering around at the same time, so the user doesn’t have to wait for the first ship to arrive before issuing a second order. This means we need a queue of navigation orders that will be processed at each update. We create an object that will store the source cell, target cell, the path the ship will take and the ship model and the ship object that carries meta data associated with the ship. At each update call we will process each item in the command queue and make the required movement to the next cell in the path. After each item in the queue is processed it gets queued again. This way all the ships movements will be updated once for every update call. If there is another ship in the next cell for the ship we are processing just skip that command item for this frame. This will make the current ship wait if there is another ship blocking the path, until the ship moves away from that cell. There is an edge case that needs to handled here, which is that if the blocking ships final cell is that cell, then the current ship will wait forever. To mitigate this case checking if any ships will end up at a cell blocking the way needs to be considered when creating the command. Processing the cells in the path of the command object is quite similar. Each update call, dequeue the next path from the paths and move towards that cell. If the ship has reached the cell, transfer the ship to that cell and discard that cell from the path. If the path queue is empty, it means we have reached our destination. So here is the algorithm outlined in a list

  1. copy the command item queue to a new queue, call it nextQueue
  2. while there are items in the queue, loop
    1. get the current command
    2. currentCell = the cell this ship is on now
    3. next cell = peek at the head of the path for the current command
    4. if there is a ship on the next cell, enqueue that command in nextQueue and continue the loop
    5. check if the ship needs a rotation to get the current cell, and process the rotation if required
    6. move the ship towards the next cell
    7. if the ship is in the next cell, transfer the ship to that cell.
    8. if there are more paths to process, requeue the current command in nextQueue
  3. copy nextQueue back to command item queue

Tags: #hexarategy #gamedev