TEXT   19

liquidwar algorithm

Guest on 17th August 2022 02:01:08 PM

  1. Liquid War (v5.6.4) - Core algorithm
  2.  
  3.  
  4.  
  5.  
  6. Introduction
  7. ============
  8.  
  9.  
  10.   General remarks
  11.   ---------------
  12.  
  13.     If you have played Liquid War, you must have noticed that your army always
  14.     takes the shortest way to reach the cursor. So the fundamental stuff in
  15.     Liquid War is path-finding. Once you've done that the game is quite easy to
  16.     code. Not harder than any other 2D game. Still the path finding algorithm
  17.     is an interesting one, for it's not a common method that we used.
  18.  
  19.     Basically, at each round (by round I mean a game logical update, this
  20.     occurs 10 or 100 times/sec depending on the level and/or your machine), the
  21.     distance from all the points of the level to your cursor is calculated. Now
  22.     the point is to calculate this fast, real fast. In fact, a "gradient" is
  23.     calculated for all the points of the level, and the value of this gradient
  24.     is the distance required for a little pixel/fighter to reach your cursor,
  25.     assuming that he takes the shortest way. Liquid War does this with a 10%
  26.     error tolerance, and it's enough for keeping the game interesting.
  27.  
  28.     Once you have this gradient calculated, it's not hard to move your
  29.     fighters. Basically, you just have to move them toward the adjacent point
  30.     that has the lowest gradient value, ie is the closest to your cursor.
  31.  
  32.   History
  33.   -------
  34.  
  35.     The Liquid War algorithm has been invented by my friend Thomas Colcombet In
  36.     fact the Liquid War algorithm has been invented before the game itself. The
  37.     game came as a consequence of the algorithm, he just thought "mmm, cool, we
  38.     could make a game with that!".
  39.  
  40.     Later, I enhanced the algorithm, as I coded it. The consequences were a
  41.     performance increase, especially on simple but big levels. I mean levels
  42.     with wide areas for teams to move. Still the basis of the algorithm
  43.     remained the same.
  44.  
  45.   Pros
  46.   ----
  47.  
  48.     The Liquid War algorithm for path-finding is very efficient:
  49.  
  50.     * When you have to move lots of different points toward one single point.
  51.       Good thing that's the rule of Liquid War!
  52.  
  53.     * When you have no clue about how your map will look like, ie if the walls
  54.       are randomly placed. The complexity of the level doesn't influence much
  55.       the speed of the algorithm. The size does, but the complexity, ie the
  56.       number of walls, is not so important.
  57.  
  58.   Cons
  59.   ----
  60.  
  61.     The Liquid War algorithm is very poor compared to other algorithms when:
  62.  
  63.     * You have several target destinations, that's to say Liquid War would be
  64.       really slow if there were 100 teams with 10 players only.
  65.  
  66.     * You want to move one single point only.
  67.  
  68.     * > You want the exact (100% sure) path. In fact, this algorithm finds
  69.       solutions which approach the best one but you can never figure out if the
  70.       solution you found is the best, and the algorithm never ends. In the long
  71.       term, the algo will always find the best solution or something really
  72.       close but I don't know any easy way to figure out when you have reached
  73.       this state.
  74.  
  75.  
  76.  
  77. Mesh
  78. ====
  79.  
  80.  
  81.   Introduction
  82.   ------------
  83.  
  84.     The first Liquid War algorithm used to calculate the gradient (the distance
  85.     from a point to your cursor) for every single point of the map.
  86.  
  87.     With Liquid War 5, I used a mesh system. This mesh system is a structure of
  88.     squares connected together. Squares may be 1,2,4,8 or 16 units large or any
  89.     nice value like that, and the gradient is only calculated once for each
  90.     square. Squares have connections between them, and each connection is
  91.     associated to a direction.
  92.  
  93.     There are 12 directions:
  94.  
  95.     * North-North-West (NNW)
  96.  
  97.     * North-West (NW)
  98.  
  99.     * West-North-West (WNW)
  100.  
  101.     * West-South-West (WSW)
  102.  
  103.     * South-West (SW)
  104.  
  105.     * South-South-West (SSW)
  106.  
  107.     * South-South-East (SSE)
  108.  
  109.     * South-East (SE)
  110.  
  111.     * East-South-East (ESE)
  112.  
  113.     * East-North-East (ENE)
  114.  
  115.     * North-East (NE)
  116.  
  117.     * North-North-East (NNE)
  118.  
  119.   Example
  120.   -------
  121.  
  122.     Well, let me give you an example, supposing that you level structure is:
  123.  
  124.     **********
  125.     *        *
  126.     *        *
  127.     *       **
  128.     *        *
  129.     **********
  130.  
  131.     The * represent walls, that's to say squares where fighters can not go.
  132.  
  133.     Then the mesh structure would be:
  134.  
  135.     **********
  136.     *11112233*
  137.     *11112233*
  138.     *1111445**
  139.     *i1114467*
  140.     **********
  141.  
  142.     In this mesh, there are 7 zones:
  143.  
  144.     * zone 1 has a size of 4. It's linked with zones 2 (ENE) and 4 (ESE).
  145.  
  146.     * zone 2 has a size of 2. It's linked with zones 3 (ENE,ESE), 5 (SE), 4
  147.       (SSE,SSW) and 1 (SW,WSW,WNW).
  148.  
  149.     * zone 3 has a size of 2. It's linked with zones 5 (SSW), 4 (SW) and 2
  150.       (WSW,WNW).
  151.  
  152.     * zone 4 has a size of 2. It's linked with zones 2 (NNW,NNE), 4 (NE), 5
  153.       (ENE), 6 (ESE) and 1 (WSW,WNW,NW).
  154.  
  155.     * zone 5 has a size of 1. It's linked with zones 3 (NNW,NNE,NE), 7 (SE), 6
  156.       (SSE,SSW), 4 (SW,WSW,WNW) and 2 (NW).
  157.  
  158.     * zone 6 has a size of 1. It's linked with zones 5 (NNW,NNE), 7 (ENE,ESE)
  159.       and 4 (WSW,WNW,NW).
  160.  
  161.     * zone 7 has a size of 1. It's linked with zones 5 (NW) and 6 (WSW,WNW).
  162.  
  163.   Why such a complicated structure?
  164.   ---------------------------------
  165.  
  166.     Because it allows the module which calculates the gradient to work much
  167.     faster. With this system, the number of zones is reduced a lot, and
  168.     calculus on the mesh can go very fast. At the same time, this mesh
  169.     structure is complicated to understand by us humans but it's very easy for
  170.     the computer.
  171.  
  172.  
  173.  
  174. Gradient
  175. ========
  176.  
  177.  
  178.   Introduction
  179.   ------------
  180.  
  181.     For each zone defined in the mesh, LW calculates an estimation of the
  182.     distance between the cursor and this zone.
  183.  
  184.     The algorihm is based on the fact that to cross a zone which size is n, n
  185.     movements are required. Easy, eh?
  186.  
  187.   Description
  188.   -----------
  189.  
  190.     Here's the way the algorithm works:
  191.  
  192.     for each turn of the game, do:
  193.  
  194.     * pick up a direction between the 12 defined directions. They have to be
  195.       chosen is a peculiar order to avoid weird behaviors from fighters, but
  196.       let's suppose we just pick up the "next" direction, ie if WSW was chosen
  197.       the last time, we pick up WNW.
  198.  
  199.     and then for each zone in the mesh, do:
  200.  
  201.     * Compare the potential of the current zone with that of its neighbor zone.
  202.       The neighbor zone to be chosen is the one which corresponds to the
  203.       direction which has been previously picked up, and by potential I mean
  204.       "the distance to the cursor, estimated by the algorithm's last pass".
  205.  
  206.     * If potential_of_the_neighbor_zone > (potential_of_the_current_zone +
  207.       size_of_the_current_zone) then potentiel_of_the_neighbor_zone =
  208.       potential_of_the_current_zone + size_of_the_current_zone
  209.  
  210.   How can this work?
  211.   ------------------
  212.  
  213.     Well, just ask my friend thom-Thom, he's the one who had the idea of this
  214.     algorithm!
  215.  
  216.     The basic idea is that by applying this simple rule to all the zones, after
  217.     a certain amount of time, it's impossible to find any place in the mesh
  218.     where the rule is not respected. And at this time, one can consider the
  219.     potiential is right in any point.
  220.  
  221.     Of course when the cursor moves the potential has to be recalculated, but
  222.     you see, cursors move really slowly in Liquid War, so the algorithm has
  223.     plenty of time to find a new stable solution...
  224.  
  225.   Demo
  226.   ----
  227.  
  228.     It's possible to see this algorithm working by typing:
  229.  
  230.     ufootgrad[n]
  231.  
  232.     while playing, where [n] is the number of the team the gradient of which
  233.     you want to view. The game is still running but you view a team's gradient
  234.     being calculated in real time instead of seeing the fighters.
  235.  
  236.     If you type ufootgrad0 the display comes back to normal mode.
  237.  
  238.  
  239.  
  240. Move
  241. ====
  242.  
  243.  
  244.   Introduction
  245.   ------------
  246.  
  247.     Once the gradient is calculated for any zone on the battlefield, it's quite
  248.     easy to move the fighters, hey?
  249.  
  250.     The following method is used to move the players:
  251.  
  252.     * A "main direction" is chosen for the fighter, this direction is chosen
  253.       using the gradient calculated on the mesh.
  254.  
  255.     * Knowing which direction is the main one, a "level of interest" is applied
  256.       to the 12 defined directions.
  257.  
  258.     There are 4 "level of interest" for directions:
  259.  
  260.     * Main directions: the direction calculated.
  261.  
  262.     * Good directions: these directions should lead the fighter to the cursor.
  263.  
  264.     * Acceptable directions: ok, one can use this direction, since the fighter
  265.       shouldn't loose any time using it.
  266.  
  267.     * Unpossible directions: wether there's a wall or using this direction
  268.       means the fighter will be farer from his cursor than before, it always
  269.       means that this direction will not be used, never.
  270.  
  271.   Rules
  272.   -----
  273.  
  274.     The fighters will try to find any matching situation in this list, and
  275.     chose the first one.
  276.  
  277.     * The main direction is available, no one on it, OK, let's follow it.
  278.  
  279.     * There's a good direction with no one on it, OK, let's follow it.
  280.  
  281.     * There's an acceptable direction with no one on it, OK, let's follow it.
  282.  
  283.     * The main direction is available, but there's an opponent on it, I attack!
  284.       By attacking, one means that energy is drawned from the attacked fighter
  285.       and transmitted to the attacker. When the attacked fighter dies, he
  286.       belongs to the team which killed him.
  287.  
  288.     * A good direction is available, but there's an opponent on it, I attack!
  289.  
  290.     * The main direction is available, but there's a mate on it, I cure him.
  291.       That's to say that energy is given to the mate. This way, when there's a
  292.       big pool of fighters from the same team, they re-generate each other.
  293.  
  294.     * None of the previous situations found, do nothing.
  295.  
  296.   Tips and tricks
  297.   ---------------
  298.  
  299.     The behavior of the armies is quite tricky to set up. I had myself to try
  300.     many algorithms before I came to something nice. In fact, I had to
  301.     introduce some "random" behaviors. They are not really random for I wanted
  302.     the game to behave the same when given the same keyboard input, but for
  303.     instance, fighters will prefer NNW to NNE sometimes, and NNE to NNW some
  304.     other times. By the way, I think Liquid War could stand as a nice example
  305.     of the thoery of chaos.

Raw Paste


Login or Register to edit or fork this paste. It's free.