next »

[PompiPompi]

I have began to tackle AI, and of course I need path finding for the AI.
The battle board looks like this:
http://www.youtube.com/watch?v=gHeLRF8TY7M

So I have a rectangle walking area. With a few rectangle hit box obstacles. The characters also have a ractangle hit boxes.
I need the AI character to be able to chase the player or other character, eventhough there are obstacles in the way. So sometimes he needs to go around them eventhough the enemy is straight ahead.
One possiblity is using djikstra and the like to calculate all possible path of all possible points. But that seems like a lot of calculations, even if it's ment to be precalculated. The obstacles are random and some obstacles may be destroyed.
Another option is to calculat A* every frame or every few frame or limited A*. Do you think I can do this fast enough? For PC sure, but for Android?
What other options can you think of?

Thanks.

[Dacke]

Will it always be 1-vs-1? Or will there be multiple units on each side, so that units must navigate around their friends as well?

[PompiPompi]

Currently it's only 1 vs 1, if you got a solution for that it's great. If in the future I want more units, then I will ahve to think of something. But for now... 1 vs 1.

[Dacke]

I have never programmed path finding that approaches a moving target in real time, so my advice may not be first rate. But I'll give it a shot anyway and hope to be corrected by someone if I mess up

How feasible is it to use Dijkstra's algorithm to calculate and store the distance from every point to every other point? I'm not sure about the answer, so let's do the math together.

What to store?
For every square in the grid, we have to compute the distance to every other square. We can then store such a distance grid for every target square. The AI can then just greedily use that information to calculate where to go. (If this isn't clear, please ask me to clarify )

If the battle board is Width wide and Height high, there are Width*Hieght squares. So there are Width*Height squares and for each we have to store Width*Height distances. This gives us Width²*Height² distances to store. If we are lazy, we will store every distance as a 32bit number (4 bytes). This gives us Width²*Height²*4 bytes of information to store.

Your battlefield looks appears to have.. say Width=22 and Height=15. This gives us 22² * 15² = 108900 values to calculate (which only have to be calculated once at the start of the level, or once when they are first needed). And 108900 * 4B = 435kB ~= 0.5MB to store.

Doing the calculations seems totally doable. It would also allow you to be really naive about the way you do you path finding during the game, which is nice. But the question is: can you afford to spend 0.5MB RAM on a path finding lookup table on an Android?

Also: you must be sure that you won't use bigger battle fields in the future. Because Width²*Height² will grow fast if you start using bigger battlefields.

edit: A good thing about this approach is that it scales very well with more units. The downside being that it scales extremely bad with bigger battlefields. For example: 200²*80²*4 B = 1GiB

edit 3: If you go with A* instead, you don't have to calculate a new path every frame. You can just recalculate the path when the enemy has moved to a new square. Which should only happen once or twice every second, making it fairly cheap.

edit 47: Everything above is based on the assumption that your bushes are aligned to a grid. If they aren't, you may require a different approach.

[PompiPompi]

Yea, the bushes arn't aligned to a grid. XD
I also learned that the "Calculate once in a second" approach isn't really helpful. Because you then end up with CPU spikes that makes your game jitter.
You can spread the calculation over several frames, make some sort of dynamic A* that constantly updates itself. Would be mind boggeling though.
The dynamic A* isn't such a bad idea...
If the source is moving, it's not too difficult to update the A* map. If the target is moving and the A* didn't reach it yet, it doesn't matter so much. If the A* already reach the target, it requires some thought.
In Addition the A * doesn't have to cover the whole map, and it could also be calculated for the general direction if it didn't reach the target yet.
I think I will start off with a plain dumb A*, and see how the PC handles it.
I have implemented an A* for the strategy board, but it's terribly slow.
Maybe you know how to implement A* really fast for the CPU? I implemented it with recursion which probably made it really slow.
Maybe even taking cash misses into account... not sure it's applicable to Android though...

[Dacke]

You are right in that "calculating once every second" won't be much use when you only have two one unit (it should help if you have 2 or more). With lots of units it should help a lot, assuming that you can afford to calculate one unit's path every frame (which you should, I think). So if you only recalculate the paths for the units that need it and spread those calculations out over the frames, you should be able to handle lots of units.

A* being terribly slow may indicate some implementation issues.
Are you using A* over pixels or over grid squares?
Implementing A* using recursion sounds strange. You should be using a priority queue, not recursion, to pick the next node to expand. So what are you using recursion for?

Could you perhaps put up some code/pseudocode for your A* implementation?

Also, given how your battlefield has very few walls and dead ends, you could benefit from using the very simple variation Weighted A*. (It just entails multiplying your heuristic with a constant)

I'm not familiar with "Dynamic A*". Could you explain it in short or had me a link?

[Dacke]

Thinking some more about it, I've come to realize that it would be pretty easy to split up an A* search over several frames. A position in the search can be defined by the content in the priority queue and a boolean array that keeps track of visited nodes. Whenever you need to take a break from the search, just stop pulling stuff from the priority queue. When you need to continue the search, just pull some more items from the queue. Easy as pie!

(But I still don't think that you should need to do that on your PC, unless something is wrong)

[PompiPompi]

Hi, I have implemented the "basic" A*. With a priority queue.
This is how it looks:
http://www.youtube.com/watch?v=Jr8D5YfEn1k

I think I want to try do a better hueristic first. I am not sure how. How would I make the search path prefer the look path? That is what I saw in the huerstic gif on wikipedia...

[PompiPompi]

Ok, I got the heuristic thing done. It appears I have always used heuristic 0, now I can choose which heuristic to choose. With the diagonal distance from goal huristic it is way faster.

[Dacke]

Oh, neat video! And great that you got it working

Without the heuristic, A* degenerates to Dijkstra's algorithm, which just tries to search every square on the grid. So it's not so surprising that it was slow

It is the goal of the heuristic to estimate "distance left to travel" as accurately as possible. I think that the best you can do here is to estimate it by using a straight line. Which, as you know, is given by the pythagorean theorem:
H = sqrt((startX - goalX)² + (startY - goalY)²)

If you want Weighted A* you can then multiply the Heuristic with constant e (that is greater than 1):
H *= e

It can result in slightly longer paths (at most e times longer), mostly in labyrinths. In your case you don't have any dead ends, so you will hardly notice it. You should experiment with it, but my guess is that it will be enough to set it to something low. Just enough to make it gravitate towards the goal even if obstructed by minor obstacles. Maybe try:
e=1.1
Which can result in up to 10% longer paths.

The difference being this:

A* with H=0

A* with proper H

Weighted A* with e=5.0

   
  

So I recommend that you try using the Heuristic:
H = 1.1 * sqrt((startX - goalX)² + (startY - goalY)²)

edit: I also want to say that I'm really enthusiastic about you making a playable Archon clone! I hope that it will come to a Linux platform that I can use (Debian/Ubuntu or Android)

[PompiPompi]

Thanks,
I will try multiplying by 1.1, I will see the resulting paths. I should probably profile it for performance. Not sure I will do it now.
The game already runs on Android, so I would probably need to do more testing when I run the AI on the phone. I think the simulation is already a bit slowing down the frame rate(On the Android).

[Dacke]

Good

It's a bit tricky to give helpful advice without access to the code. But if you ever decide to publish your code (which I believe everyone should do), I'll be happy to give some more concrete input and perhaps contribute code as well

[PompiPompi]

Ok, back to this topic, heh.
I seem to have issues with trying to do a non trivial Heuristic. Not sure it's even possible.
The behaviour I want to achieve is having the AI character keep a distance(some sort of const) with the player, while avoiding obstacles. I did a heuristic that is simpley calculating the air distance from the player, but subtracts a constant distance from this value and use abs on it.
Instead of having one point with a global minimum(0) like in the chase heuristic, now I have a circle of 0 values. I think it doesn't work so well this way, but it works sometimes.
After accomplishing that, I want a more advanced technique in which the AI character keeps a distance, avoid obstacles, but also have a clear eye sight of the player(no obstacles between the player and the AI character).
I tried several things, but it doesn't seem to work so well.
Any idea how to achieve this?

[Dacke]

Up until now, you have told A* to go to a specific coordinate (x, y).

Conceptually you can instead do this:
Define the target as a set of goal coordinates [(x1, y1) (x2, y2) (x3, y3) ...]. Then have A* try to find it's way to one of those.

• The "distance travelled" part would be the same as usual.
• The heuristic would just be calculating all the distances to the possible goals and choosing the closest one.
• The algorithm would quit when it has reached one of the coordinates.

So if you want to go to a specific distance of the enemy, you just use all the coordinates that lie on that circle as the target. Computationally, it may be too costly to let the heuristic look through all those target coordinates over and over. So if you need to, you can instead send in the circle (x, y, radius) that defines the target coordinates and calculate the heuristic from that.

If you want to get to a specific distance of the enemy and have a line of sight, you just give it the coordinates that fulfil both those criteria. To make this computationally cheaper, you can send in a circle that defines the distance from the enemy as well as the list of the coordinates that actually work. That way, you can first check the distance to the circle and then confirm it with the list. If the list says that the closes point on the circle lacks line of sight, check with the second closest point on the circle (and so on)

[PompiPompi]

I actually solved the keep a distance heuristic, I don't know why it works this way, but this is my line of thought.
At first I gave some Heuristic, as I described, it didn't work well. Then I thought, maybe I will just switch between chase and flee heurstics depending on distance? I thougt to do it per frame, for the starting point of the character. But then I tried soemthing else. when the current position is closer to the player then the constant distance, I will give it the flight distance with a minus sign as a heuristic(like in the flee heuristic). When the current position is farther than the constant distance from the player, I will give it a positive flight distance prediction(like in the chase heuristic).
This somehow works perfectly.
Which means the heuristic has a discontinuity between negative and positive exacctly at the circle with the constant distance from the player. I also gave it a stop condition in case it's in the right distance.
I still need to tackle the open line sight, but I think your idea of giving a list of acceptable points might help.