Simple but efficient pathfinding AI

[assasinDN]

Hello fellow java lovers. So I have been working on a zombie up side down game. Mostly for the purpose of learning. I have come to the stage of development where the AI needs to be upgraded. My current AI for the zombies is very simple. They simple walks towards the angle of the players current location. This method has many problems, cleary. They cant walk around walls and they walk inside of eachother (I tried creating a collision between the zombies, but it glitched out quite a bit). So I have been reading fairly much on the subject of AI lately, especially on A* algorithm. But I have had problems trying to implementing it.

So now to my question('s). The game box head ( http://www.y8.com/games/box_head_2play ) have a good pathdinding algorithm, or atleast I think so. And the game I'm working on is fairly simmilar to it. What pathfinding AI do you think the game uses? And could you give me some resources to help me on my way?

Thanks for reading.

[ctomni231]

AI is an advanced topic, but it isn't impossible. A* got its popularity for a reason, it is a very quick way of getting entities to realize walls and pathfind their way to entities. There is no doubt that Box Head probably used A*. There is a pretty good tutorial within this site but the page I love to reference is here...

Coke &Code Pathfinding

If I were you, I'd look into implementing aabb collisions for all objects first. Make sure they can't overrun each other before implementing A*. Make sure all your entities are following the rules of your game world before implementing any path finding algorithm. If the collisions are a bit complicated, then attempt using an engine like Box2d to handle it, and implement A* over it.

In short, game rules are always more important to a game than pathfinding. Always try to break down your game engine into small parts to help you design faster.

[saucymeatman]

Boxhead rules!
Cant wait to see your game.

Games published by our own members! Check 'em out!

[Nate]

There's this:
https://gist.github.com/NathanSweet/7587981

[assasinDN]

AI is an advanced topic, but it isn't impossible. A* got its popularity for a reason, it is a very quick way of getting entities to realize walls and pathfind their way to entities. There is no doubt that Box Head probably used A*. There is a pretty good tutorial within this site but the page I love to reference is here...

Coke &Code Pathfinding

If I were you, I'd look into implementing aabb collisions for all objects first. Make sure they can't overrun each other before implementing A*. Make sure all your entities are following the rules of your game world before implementing any path finding algorithm. If the collisions are a bit complicated, then attempt using an engine like Box2d to handle it, and implement A* over it.

In short, game rules are always more important to a game than pathfinding. Always try to break down your game engine into small parts to help you design faster.

At the moment I am using Rectangle intersects method for my collision system. Never had heard of the aabb algorithm. I just read a piece on this forum about it. What are the benifits besides performance? Is it a smoother system in terms of AI and pathfinding?

I have read a few tutorials on it now. So lets say, I have a two dimensional array which symbolises my map. Each value in the array represents a tile. How should I translate this to A* checking if the tile is walkable or not? My Idea of A* is the algorithm checking all 9 tiles around and including the starting node / tile for the smallest F value. I will have to read the article you linked when I get home from school, thanks!

Boxhead rules!
Cant wait to see your game.

Thanks man, yaeh I got addicted to that game a few years ago.

There's this:
https://gist.github.com/NathanSweet/7587981

Thanks, but I'm programming in Java2D. This is my first "real" game, so want to be familiar with good old jave before I'm throwing myself in some openGL mess.

[Opiop]

Ok here we go!

AABB
Stands for Axis Aligned Bounding Box and is used for collision detection. Why? Its a very simple and, one could day, fast algorithm because it only deals with boxes that have no rotation. If you want rotation in your game, consider using the Separating Axis Theorem!

AABB collision detection basically works like this:
Check to see if the "x" of this box is greater than the "x" of that box. Repeat for the "y" axis. Then check to see if the "x" position is less than the "x + width" of the box you're checking against, repeat for the "y" axis. And because that made little sense, here's the math:

if x > other.x
If y > other.y
If x < other.x + other.width
If y < other.y + other.height

Very simple right? Now there are other ways to do it, but that's the easiest way.

As for your question about tiles. There are many many ways to store and use tile objects, I personally use a static based byte id system, but that's over your head. What you should do is create a Tile class that contains common methods that every tile will use. One of those should be an "isSolid" method. The method will simply return a boolean based on whether or not the player can move through it.

Hopefully that helped, sorry I can't exactly walk you through the A* algorithm!

Edit:
Here's a great article that explains A* very thoroughly:
http://www.policyalmanac.org/games/aStarTutorial.htm

[Nate]

Thanks, but I'm programming in Java2D. This is my first "real" game, so want to be familiar with good old jave before I'm throwing myself in some openGL mess.

Then ignore the libgdx specific stuff. Astar isn't specific to a game toolkit. However, you are unnecessarily punishing yourself by trying to use Java2D, IMHO.

[SilverTiger]

In my C# Client I used a simple Pathfinding algorithm, maybe it'll help you!
First I have to say that I had an Array which contained the Tiles.
I went through that map array and made a boolean array where tile(x,y) = true if it was walkable, else it was false.
After that I made an array which contained the distances from the end point to the other tiles, I used that array then to form a path.

It isn't the ideal pathfinding, but it is rather simple to implement.
Now there we go:
http://pastebin.java-gaming.org/fb985144580

How does it work? Here is a simple example:
S is the start point and E of course the end point, x is not walkable.

1   2   3   4

[ ] [S] [ ] [ ] [x] [ ] [x] [x] [ ] [ ] [x] [ ] [ ] [ ] [ ] [E]

Now that's our start, now we look starting at the end point how much steps we need to any other tile:

1   2   3   4

[6] [5] [7] [8] [x] [4] [x] [x] [4] [3] [x] [1] [3] [2] [1] [0]

Then we just take the shortest Path in descending order: 5/S -> 4 -> 3 -> 2 -> 1 -> 0/E

1   2   3   4

[6] [S] [7] [8] [x] [▼] [x] [x] [4] [▼] [x] [1] [3] [►] [►] [E]

I hope I didn't forget something or mixed it up... Glad if it'll help you a little with that pathfinding

[assasinDN]

Sorry for being inactive, have had alot of school recently so majority of my free time have gone to study and such. Hopefully I will be free for the upcoming days so I will be able to sit down and trying to figure it all out. When I have more concrete questions I will update you all with my mess. Thanks for the help, guys.