Well, let me give you an example, supposing that you level structure is: Squares have connections between them, and each connection is associated to a direction. 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. This mesh system is a structure of squares connected together. 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. In the long term, the algo will always find the best solution or something really close but I don't know any easy way to figure out when you have reached this state. In fact, this algorithm finds solutions which approach the best one but you can never figure out if the solution you found is the best, and the algorithm never ends. > You want the exact (100% sure) path.You want to move one single point only.You have several target destinations, that's to say Liquid War would be really slow if there were 100 teams with 10 players only.The Liquid War algorithm is very poor compared to other algorithms when: The size does, but the complexity, ie the number of walls, is not so important. The complexity of the level doesn't influence much the speed of the algorithm. When you have no clue about how your map will look like, ie if the walls are randomly placed.Good thing that's the rule of Liquid War! When you have to move lots of different points toward one single point.The Liquid War algorithm for path-finding is very efficient: Still the basis of the algorithm remained the same. I mean levels with wide areas for teams to move. The consequences were a performance increase, especially on simple but big levels. Later, I enhanced the algorithm, as I coded it. The game came as a consequence of the algorithm, he just thought "mmm, cool, we could make a game with that!". 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. Basically, you just have to move them toward the adjacent point that has the lowest gradient value, ie is the closest to your cursor. Once you have this gradient calculated, it's not hard to move your fighters. Liquid War does this with a 10% error tolerance, and it's enough for keeping the game interesting. ![]() 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. Now the point is to calculate this fast, real fast. Still the path finding algorithm is an interesting one, for it's not a common method that we used.īasically, 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. Once you've done that the game is quite easy to code. So the fundamental stuff in Liquid War is path-finding. If you have played Liquid War, you must have noticed that your army always takes the shortest way to reach the cursor.
0 Comments
Leave a Reply. |