Core algorithm

Introduction

General remarks

If you have played Liquid War, you must have noticed that your army always takes the shortest way to reach the cursor. So the fundamental stuff in Liquid War is path-finding. Once you've done that the game is quite easy to code. Not harder than any other 2D game. Still the path finding algorithm is an interesting one, for it's not a common method that we used.

Basically, at each round (by round I mean a game logical update, this occurs 10 or 100 times/sec depending on the level and/or your machine), the distance from all the points of the level to your cursor is calculated. Now the point is to calculate this fast, real fast. In fact, a "gradient" is calculated for all the points of the level, and the value of this gradient is the distance required for a little pixel/fighter to reach your cursor, assuming that he takes the shortest way. Liquid War does this with a 10% error tolerance, and it's enough for keeping the game interesting.

Once you have this gradient calculated, it's not hard to move your fighters. Basically, you just have to move them toward the adjacent point that has the lowest gradient value, ie is the closest to your cursor.

History

The Liquid War algorithm has been invented by my friend Thomas Colcombet In fact the Liquid War algorithm has been invented before the game itself. The game came as a consequence of the algorithm, he just thought "mmm, cool, we could make a game with that!".

Later, I enhanced the algorithm, as I coded it. The consequences were a performance increase, especially on simple but big levels. I mean levels with wide areas for teams to move. Still the basis of the algorithm remained the same.

Pros

The Liquid War algorithm for path-finding is very efficient:

Cons

The Liquid War algorithm is very poor compared to other algorithms when:

Mesh

Introduction

The first Liquid War algorithm used to calculate the gradient (the distance from a point to your cursor) for every single point of the map.

With Liquid War 5, I used a mesh system. This mesh system is a structure of squares connected together. Squares may be 1,2,4,8 or 16 units large or any nice value like that, and the gradient is only calculated once for each square. Squares have connections between them, and each connection is associated to a direction.

There are 12 directions:

Example

Well, let me give you an example, supposing that you level structure is:

  **********
  *        *
  *        *
  *       **
  *        *
  **********

The * represent walls, that's to say squares where fighters can not go.

Then the mesh structure would be:

  **********
  *11112233*
  *11112233*
  *1111445**
  *i1114467*
  **********

In this mesh, there are 7 zones:

Why such a complicated structure?

Because it allows the module which calculates the gradient to work much faster. With this system, the number of zones is reduced a lot, and calculus on the mesh can go very fast. At the same time, this mesh structure is complicated to understand by us humans but it's very easy for the computer.

Gradient

Introduction

For each zone defined in the mesh, LW calculates an estimation of the distance between the cursor and this zone.

The algorihm is based on the fact that to cross a zone which size is n, n movements are required. Easy, eh?

Description

Here's the way the algorithm works:

for each turn of the game, do:

and then for each zone in the mesh, do:

How can this work?

Well, just ask my friend thom-Thom, he's the one who had the idea of this algorithm!

The basic idea is that by applying this simple rule to all the zones, after a certain amount of time, it's impossible to find any place in the mesh where the rule is not respected. And at this time, one can consider the potiential is right in any point.

Of course when the cursor moves the potential has to be recalculated, but you see, cursors move really slowly in Liquid War, so the algorithm has plenty of time to find a new stable solution...

Demo

It's possible to see this algorithm working by typing:

  ufootgrad[n]

while playing, where [n] is the number of the team the gradient of which you want to view. The game is still running but you view a team's gradient being calculated in real time instead of seeing the fighters.

If you type ufootgrad0 the display comes back to normal mode.

Move

Introduction

Once the gradient is calculated for any zone on the battlefield, it's quite easy to move the fighters, hey?

The following method is used to move the players:

There are 4 "level of interest" for directions:

Rules

The fighters will try to find any matching situation in this list, and chose the first one.

Tips and tricks

The behavior of the armies is quite tricky to set up. I had myself to try many algorithms before I came to something nice. In fact, I had to introduce some "random" behaviors. They are not really random for I wanted the game to behave the same when given the same keyboard input, but for instance, fighters will prefer NNW to NNE sometimes, and NNE to NNW some other times. By the way, I think Liquid War could stand as a nice example of the thoery of chaos.

Page generated by UWiKiCMS 1.1.4 on Sat Nov 22 2014.
Copyright © 2005 Christian Mauduit. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
Updated on Sat May 07 2005.