Mass AI: What should I do?

ID:151584
 
Feb 10 2010, 3:06 am
I'm making a defense game entitled War of Legend. Basically, you control medieval units, and the objective is to kill the enemy ruler(which is either a Prince, Princess, King, Queen, Demi-God,Demi-Goddess, God, Goddess, or Titan) or take the main base(s). You can have up to 75 units on the field at one time.

My question is what is the least laggy, if not lagless way to do this? Theodis's Dijkstra Pathfinder demo won't work, simply because when you combine that with all of the other AI procs running at a time(such as if your unit is standing ground, then ward off enemies which come within 4 tiles). However, I can't even make that version work, ontop of that, when the procs are running(even with the background setting, and a sleep) it lags with just two units!

What could I to manage such AI, without having the AI look ridiculous? Would it be easier to just have paths placed on the map? What should I do?
Feb 10 2010, 4:27 am
Can you explain how your game works a bit more and what specific conditions the pathfinder is working on? Generally you can avoid mass pathing by handling it in groups like if you have a group of units with the same destination you could solve a path for one unit and have the rest follow that unit. If it dies designate another as the leader and resolve the path or find your way back to one of the nearby nodes of the original. If the map is static or predictably dynamic it may be possible to just precompute common or most likely paths and make use of those.

Also make sure you are using the correct pathfinding algorithm for the job which is generally A*. For A* you need a start, a known destination, and a reasonable distance estimate between the current location and the destination(usually simply just the get_dist() between the current location and destination). That eliminates much of the search area because it'll prioritize searching in the direction of the target. Dijkstra on the other hand evenly searches outward so it tends to search a much larger area. It's more useful when you don't know the exact position of the destination but will know when you see it or if you have one starting location and need to simultaniously solve multiple paths.

After deciding on the right algorithm you can further optimize the pathfinding by making sure your get nodes and distance procs are as simple as possible because they get called a lot. Some things which seem fast when done once can really bog things down when you try and call them thousands of times a second. Avoid doing things which generate complicated lists or call other BYOND procs(hard coded built in stuff is in general reasonably cheap) so look up what you're using. So avoid stuff like view(), range(), etc. block() for instance runs faster.

Anyway I need to run out and catch a bus. I'll edit and finish my post shortly :P. So if there are any typos of grammar errors no harassing me.
Feb 10 2010, 5:56 am
In response to Theodis
Theodis wrote:
Can you explain how your game works a bit more and what specific conditions the pathfinder is working on? Generally you can avoid mass pathing by handling it in groups like if you have a group of units with the same destination you could solve a path for one unit and have the rest follow that unit. If it dies designate another as the leader and resolve the path or find your way back to one of the nearby nodes of the original. If the map is static or predictably dynamic it may be possible to just precompute common or most likely paths and make use of those.

A related option, that solves the problem of units blocking each other, is to consider mobs with the same target non-blocking and only impose a small path cost for moving through them. If you do find a mob along the chosen path who has the same destination, designate them the leader for a few ticks and assign the path to them, and have the other mobs move generally toward that point. Differences in unit speed could be a minor issue if the lead mob is slow, but if everyone is trying to catch up to that point you should eventually be able to path around it.

Of course there's more to this than simple pathfinding, because any squad or group is going to be far more effective in a formation. If they all come through a bottleneck and approach their target single-file, they're a lot less effective than if the leader waits for the others to catch up. So not only is A* pathfinding important, but some kind of flocking algorithm would be important as well in a game of this kind.

After deciding on the right algorithm you can further optimize the pathfinding by making sure your get nodes and distance procs are as simple as possible because they get called a lot. Some things which seem fast when done once can really bog things down when you try and call them thousands of times a second. Avoid doing things which generate complicated lists or call other BYOND procs(hard coded built in stuff is in general reasonably cheap) so look up what you're using. So avoid stuff like view(), range(), etc. block() for instance runs faster.

In SotS II, my pathfinding is optimized by storing info in associative lists, and the lowest-distance turfs are kept in a heap, which makes sorting them fast. The NPC AI only does pathfinding for a short distance before recomputing, which gives a significant speed savings. This works because 1) the AIs don't know the terrain until they've seen it, and 2) they can always shoot through walls if they absolutely have to (it's built into their path cost).

But I imagine some games, where the terrain can't be changed for instance, could lead that kind of AI into a dead end, so for those kinds of games probably I'd pre-compute some waypoints between major sections of the map so AI generally knows which direction it needs to head in rather than computing tile by tile.

Lummox JR
Feb 10 2010, 2:12 pm
In response to Lummox JR
When you say put it into heaps(The short distances) do you mean something like... have the Associative list, and then make them move to the short distances, and then reset the lists?
Feb 10 2010, 3:27 pm
In response to Jamckell
Feb 10 2010, 3:36 pm
In response to Garthor
I know what a heap is, I don't know how it could be applied here e.e...
Feb 10 2010, 7:41 pm
In response to Jamckell
Jamckell wrote:
When you say put it into heaps(The short distances) do you mean something like... have the Associative list, and then make them move to the short distances, and then reset the lists?

It works something like this: A* pathfinding requires two sorted lists of turfs, one "open" and one "closed", each of which I can keep in a datum. In the datum I have an associative list which is the heap, and then I have a separate data list that stores info about the turf like its cost and heuristic.

The data list is associative. data[T] is always set to T's position in the data list. Then I grab that index if I'm looking up the turf (i=data[T]), and data[i+1] is its cost, data[i+2] is its heuristic. (I forget now but I might be actually keeping cost+heuristic in one of those as a shortcut.)

The heap list is also associative; heap[T] is the cost+heuristic. However this list uses a min-heap sort. Maintaining a heap requires only simple bubble-up and trickle-down operations. The way the heap is arranged is like a compact tree. Index 1 is the root of the tree (the "minimum" item), index 2 is its left branch, 3 is its right branch, etc. For each index, index*2 is the left, index*2+1 is the right, and round(index/2) is the parent.

In a bubble-up, you start with an index that will be bubbling and loop until it reaches 1. During the loop, the item is compared to the item at round(index/2), and if it's not smaller the loop stops; otherwise the two indexes are swapped, and it keeps going from the new index.

In a trickle-down, at each step you compare the item to its two children (it may only have one). If it's no bigger than either child, or there are no child branches, the loop ends. Otherwise, you swap with the smaller child and keep going.

These are my bubble/trickle procs from the /pathheap datum:

proc/TrickleDown(i)
  var/j,item=heap[i],jtem,ktem
  while(i)
    j=i+i
    if(heap.len<j) return
    jtem=heap[j]
    ktem=heap[(heap.len>j)?(j+1):j]
    if(data[item]<=data[jtem] && data[item]<=data[ktem]) return
    if(data[ktem]<data[jtem]) ++j
    heap.Swap(i,j)
    i=j
    ++.

proc/BubbleUp(i)
  var/j,item=heap[i],jtem
  while(i>1)
    j=round(i/2)
    jtem=heap[j]
    if(data[item]>=data[jtem]) return
    heap.Swap(i,j)
    i=j
    ++.


When placing an item in the heap, you just have to add it to the end of the list, give it an associated value, and then bubble up.

When removing an item, you swap it with the end of the list and then chop off the end of the list. The item you swapped into its place needs to be trickled down, but if it doesn't trickle down then it has to be bubbled up. Since both routines return a true value if they did anything, you can use a line like if(!TrickleDown(pos)) BubbleUp(pos) to get the job done. (The only exception to this is that if the item you removed was already at the end of the list, you don't need to do anything except chop off the end; swapping and bubbling are irrelevant.)

The only other important operation is changing the associated value of an item already in the heap, in which case you need to try trickling down first and if that fails, bubble up; this works just like with removing an item.

The nice thing about using a heap is that at any given time, heap[1] always has the turf I want to test next in my pathfinding algorithm. I don't really care if the list is in a fully sorted order because I'm only ever working with the minimum.

Lummox JR
Feb 11 2010, 7:29 am
In response to Lummox JR
Your code is hideous. I'm not saying that it's bad, mind you. I'm saying that it's just ugly.
Feb 11 2010, 9:05 am
In response to Vermolius
Vermolius wrote:
Your code is hideous. I'm not saying that it's bad, mind you. I'm saying that it's just ugly.

In terms of spacing I concede your point. Putting more space around the operators and such would improve readability. In terms of elegance I disagree.

However I've seen much, much more hideous code in my time. Some of which I've written myself.

Lummox JR
Feb 15 2010, 6:21 am
In response to Lummox JR
Uhhh... forgive my tardiness in relpy, but... what you're saying doesn't make any logical sense. Open and closed? Could you explain which turfs are open and which is closed? Or maybe break it down and not just tell me what's happening :D Because so far all I got was... it picks from open and closed.. Saves variables like open and heuristic.. which I don't know what that is either.. in another list. And the- I don't get it.
Feb 15 2010, 8:03 am
In response to Jamckell
Jamckell wrote:
Uhhh... forgive my tardiness in relpy, but... what you're saying doesn't make any logical sense. Open and closed? Could you explain which turfs are open and which is closed? Or maybe break it down and not just tell me what's happening :D Because so far all I got was... it picks from open and closed.. Saves variables like open and heuristic.. which I don't know what that is either.. in another list. And the- I don't get it.

Open and closed lists are at the heart of A* pathfinding.

In A* pathfinding, you have two lists of nodes (turfs): open and closed. Each node has a cost to get there from the start position (calculated as you go), a heuristic representing the estimated distance from that node to the endpoint, and a link to the node you used to get there. The open list represents turfs that you have not looked at yet in terms of considering them for the path. The closed list is a list of nodes you have already considered, which may or may not be part of the path you'll choose.

The open list starts out with all the nodes you can immediately reach from your start position. Each one has its cost calculated (usually just 1 step, maybe sqrt(2) if it's a diagonal or somethin glike that), and the heuristic only needs to be calculated one time per node. The heuristic used most often in A* is the direct straight-line distance from that node to the endpoint. Terrain costs can factor in here, so if you have varying terrain you might multiply the heuristic by some average terrain value and the cost would be calculated by the terrain cost of the step. E.g., moving through swamp might have a much higher cost than moving through a light forest.

In the algorithm, each iteration you'll pull the node with the lowest cost+heuristic from the open list. You then take a look at all the nodes you can reach from there. Any that you have not yet considered go on the open list. If you find one that is already on the open list, see if you can reach it from the current node at a lower total cost, and if so update its cost. If the node is on the closed list, and you have found a lower-cost way to get there, move it back to the open list with its new, updated cost. Finally, the node you're currently at can be moved to the closed list.

Once you reach the endpoint, the algorithm is finished. You can trace back the full path you need to get there, or just take the next step and throw the rest of the path away. With a lot of AIs running around, your best bet is to do this infrequently and save either the whole path or a decent-sized part of it. They can always reconsider after a while or if they run into an obstacle due to the terrain changing.

The reason I use heaps in SotS II's pathfinding is that because you want the lowest cost+heuristic from the open list, it makes sense to store those values in a min-heap, where the lowest value is always easy to reach.

Lummox JR
Feb 15 2010, 3:34 pm
In response to Lummox JR
Lummox JR wrote:
The open list starts out with all the nodes you can immediately reach from your start position. Each one has its cost calculated (usually just 1 step, maybe sqrt(2) if it's a diagonal or somethin glike that), and the heuristic only needs to be calculated one time per node. The heuristic used most often in A* is the direct straight-line distance from that node to the endpoint. Terrain costs can factor in here, so if you have varying terrain you might multiply the heuristic by some average terrain value and the cost would be calculated by the terrain cost of the step. E.g., moving through swamp might have a much higher cost than moving through a light forest.

The heuristic must be <= to the actual cost to get to the endpoint, so you can't just multiply it by the average terrain movement cost. You'd have to multiply it by the minimum terrain movement cost, in fact.
Feb 15 2010, 4:45 pm
In response to Garthor
Garthor wrote:
The heuristic must be <= to the actual cost to get to the endpoint, so you can't just multiply it by the average terrain movement cost. You'd have to multiply it by the minimum terrain movement cost, in fact.

I don't think that's necessarily true. As long as the heuristic is correctly higher when you're further from the goal and lower when you're closer, it shouldn't matter. Since you can make the algorithm run until the goal is reached, and it always looks for the lowest cost+heuristic on the open list, all you really need to do is change the conditions under which the goal is considered unreachable.

But, it's been a while since I've studied the mathematical precepts behind this so there may be a wrinkle I'm not considering. Anyway, it's possible to look up A* pathfinding to find out for sure.

Lummox JR
Feb 16 2010, 12:41 am
In response to Lummox JR
Well, the difference is that, if the heuristic never underestimates (is "admissible"), the algorithm never needs to check the closed list. I suppose it still works, but is more complicated and a bit slower.

I'm not sure if the savings from a better but non-admissible heuristic could out-weigh the algorithm being slowed down by having the query the closed list.
Feb 19 2010, 1:14 pm
In response to Lummox JR
Basically.. move to the lowest-cost, lowest-distance turfs, and then call A* again so that less nodes are processed at one time?
Feb 19 2010, 1:32 pm
In response to Jamckell
Jamckell wrote:
Basically.. move to the lowest-cost, lowest-distance turfs, and then call A* again so that less nodes are processed at one time?

You're better off using A*, grabbing the early part of the path it gives you, and having your AIs follow that blindly until something impedes them or something else comes up which might force a change in their goals. I do this in SotS II to pretty good effect; the NPC AI seems to be a lot less costly than the Stickster's.

Lummox JR