Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (109)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Simple but efficient pathfinding AI  (Read 1742 times)
0 Members and 1 Guest are viewing this topic.
Offline assasinDN

Senior Newbie


Exp: 4-6 months



« Posted 2014-02-16 20:15:47 »

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. Smiley
Offline ctomni231

JGO Wizard


Medals: 98
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #1 - Posted 2014-02-16 20:35:45 »

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.

Offline saucymeatman
« Reply #2 - Posted 2014-02-16 22:22:08 »

Boxhead rules!
Cant wait to see your game.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Nate

JGO Kernel


Medals: 145
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #3 - Posted 2014-02-17 01:47:38 »

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

Offline assasinDN

Senior Newbie


Exp: 4-6 months



« Reply #4 - Posted 2014-02-17 12:25:26 »

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. Tongue


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.
Offline opiop65

JGO Kernel


Medals: 153
Projects: 7
Exp: 3 years


JumpButton Studios


« Reply #5 - Posted 2014-02-17 13:19:59 »

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

Offline Nate

JGO Kernel


Medals: 145
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #6 - Posted 2014-02-17 16:42:09 »

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.

Offline SilverTiger

Junior Member


Medals: 4
Exp: 2 years


がんばってください!


« Reply #7 - Posted 2014-02-17 19:23:19 »

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 Smiley
Offline assasinDN

Senior Newbie


Exp: 4-6 months



« Reply #8 - Posted 2014-02-24 18:00:26 »

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. Smiley
Pages: [1]
  ignore  |  Print  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CogWheelz (15 views)
2014-08-01 22:53:16

CogWheelz (15 views)
2014-08-01 22:51:43

CopyableCougar4 (16 views)
2014-08-01 19:37:19

CogWheelz (19 views)
2014-07-30 21:08:39

Riven (27 views)
2014-07-29 18:09:19

Riven (16 views)
2014-07-29 18:08:52

Dwinin (14 views)
2014-07-29 10:59:34

E.R. Fleming (35 views)
2014-07-29 03:07:13

E.R. Fleming (13 views)
2014-07-29 03:06:25

pw (44 views)
2014-07-24 01:59:36
Resources for WIP games
by CogWheelz
2014-08-01 18:20:17

Resources for WIP games
by CogWheelz
2014-08-01 18:19:50

List of Learning Resources
by SilverTiger
2014-07-31 18:29:50

List of Learning Resources
by SilverTiger
2014-07-31 18:26:06

List of Learning Resources
by SilverTiger
2014-07-31 13:54:12

HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!