Monthly Archives: October 2018

Progress Report: September 2018

The focus of September was on AI ship movement, mainly on path finding.

There are a lot of common path finding algorithms out there but there is one drawback they have:  while they can take some  information like terrain movement cost into consideration, they generally just find the shortest way assuming an agent could move however he wanted. This also means that they can’t calculate a path considering possible agent restrictions like that the agent can’t fully slow down (or only with some delay), an agent might have a limited turn rate and only be able to turn whilst also moving forward, etc.
Another thing they can’t do, for example, would be to also consider the wind direction and it’s influence on ship speed, to calculate the quickest/best path.

Unfortunately,  an algorithm supporting all this would most likely be not only be computationally too expensive but also out of my league, time and ability wise.

So, what I opted for instead was the following idea: I use some standard path finding but instead of just moving ships along this optimal path, I’ll try to stick to the optimal path as much as possible but will only move/rotate the ship as much as the calculated restrictions allow. For example, when the calculated path tells me the ship should rotate 5° in a frame and the ship can only rotate 3° considering alignment to wind, wind speed, etc. I only rotate the ship 3° and will then try to rotate the rest in the next frame.

Following, you can see a video where I try this out with different turn rate settings. One important thing to note is that, at least currently, the ship can’t slow down and will always move as fast as possible as it can under the current circumstances (wind direction, etc), which further exacerbates the problems you’ll witness. This isn’t entirely realistic but might be kept for game play reasons. But even if not, the ship would most likely still have some inertia that will keep it from slowing down instantly.

Things to note

  • As long as there are no tight turns, movement works flawlessly.
  • Tight turns pose big problems.
  • With higher turn speeds, the problems become fewer but are still present.
  • There are situations in the video. where you can see the problem I described in the beginning: Since it has problems making quick turns, it would make way more sense for the ship to continue sailing around an obstacle and make a soft turn instead of trying to immediately turn around. But because traditional path finding calculates what it determines the most ideal path without considering the ships slow turning speed, the calculated path is totally different and causes the ship to do an almost 180° turn practically on the spot.
    This picture shows the problem as well:

    Traditional path finding doesn’t always lend itself to finding paths that make sense for a ship… (Yellow line = desired path, end of line = desired destination)

Why this might not matter

I currently won’t try to fix this for a few reasons:

  • The ship stats/controls aren’t calibrated at all. As long as I don’t at least roughly know, how the ships will steer in the end, there’s no sense in optimizing an AI for it.
  • Luckily, naval fights mainly consist of loads of water and the occasional “Arrrh!”. There simply will be near to no obstacles at all. At most a few ships and the rest is open space.
    If there are practically no obstacles, having problems with avoiding them might simply not matter. But to be sure, I’ll have to develop a simple naval battle AI first.

What if it matters after all?

I do have some ideas on how I could fix or at least lessen this problems:

  • Ships could slow down and try to rotate in a smaller arc if the amount they want to rotate is greater than a certain amount of degrees.
  • Ships could not rotate when too close to an object so they don’t crash into it, etc.
  • I could try to calculate paths from a spot a little in front of the ship to the desired destination and use that path if it contains fewer path segments than the currently calculated path.
  • etc.