Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) 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
 AI path finding on non tile based game?  (Read 21498 times) 0 Members and 1 Guest are viewing this topic.
FewCode

Senior Newbie

Medals: 1
Exp: 3 years

 « Posted 2014-03-15 00:45:22 »

Hello there.

I know this has been asked before, but it hasn't quite answered my question.

So, I am trying to find out how to get path finding working with AI on my game. I honestly just started programming this game and after a few weeks came across this problem.

The game itself is not a tiled based game, though it looks like one and the "walls" (or collide-able objects) are placed in a tiled way. (at this point) I did consider turning it into a tile based game, but the problem comes in when you make a map in the in-built level creator. It allows the walls to be placed anywhere at all. not on tiles. it also allows the square walls to be rotated. Walls can also be destroyed.

So, here is an example of what one user made map might look like. (this one is without rotation and every wall is locked to the tiles for simplicity right now)

How can my enemy (Green square) get to the player? (yellow square) while avoiding the walls (red areas)

Now, every object in the game has a set of properties. so far the one that is the most useful for this is the objects bounds (so a rectangle of their: x, y, width and height) Hopefully I can use this to calculate their path around walls. In the game there will be different types of enemies, in different sizes, so one path might not work with all.

I do admit I will probably need to use some form of the A* method. but in that case i would have to generate "nodes" in places where it would be needed. I am not sure where to start with that.

Thank you for the help in advance. If i need to add more info, please ask and will be happy to reply with it.
jonjava
 « Reply #1 - Posted 2014-03-15 01:24:46 »

you could create an approximated tiled block map based on the level and do a A* pathfinding on that block map.

Does the AI really have to be that precise for the enemies though? You could get away with something more rudimentary.

FewCode

Senior Newbie

Medals: 1
Exp: 3 years

 « Reply #2 - Posted 2014-03-15 01:28:22 »

It doesn't need to be too advanced. In-fact its probably best not to since there could be a lot on the map at once. I have never done pathfinding at all, so i have no idea where to start. that's my problem right now.
 Games published by our own members! Check 'em out!
Opiop
 « Reply #3 - Posted 2014-03-15 01:39:48 »

You're going to need to split your map up into a grid anyway. That's how basic A* works.
FewCode

Senior Newbie

Medals: 1
Exp: 3 years

 « Reply #4 - Posted 2014-03-15 01:44:39 »

A* was just a suggestion, if there was a better way to do it, then that would be nice. I just wanna know any suggestions on how to get the enemy to the player.
Opiop
 « Reply #5 - Posted 2014-03-15 01:45:41 »

I don't see why you think it wasn't a suggestion. Plenty of people use it, it's not that hard to implement.
FewCode

Senior Newbie

Medals: 1
Exp: 3 years

 « Reply #6 - Posted 2014-03-15 01:47:05 »

Its more of, i don't know how to implement it in my game.
Opiop
 « Reply #7 - Posted 2014-03-15 01:48:26 »

Obviously, so you need to learn how to implement it. Path finding is difficult, you aren't just going to be able to implement it in 5 minutes. Here's a link to the best A* article on the internet:
http://www.policyalmanac.org/games/aStarTutorial.htm
FewCode

Senior Newbie

Medals: 1
Exp: 3 years

 « Reply #8 - Posted 2014-03-15 01:56:25 »

ok, maybe i could ask, How do i split up my map into a grid based map and link paths?
I know how A* should work. its more the way its implemented that finds the player that is hard.
jonjava
 « Reply #9 - Posted 2014-03-15 03:43:26 »

Well, for instance, decide on the grid/tile size. Let's say 8x8 in pixels.

What's the size of your level? Let's say it's 1000x600.

Basic maths gives us the size in grids now: (1000 / 8) x (600 / 8) = 125 x 75.

Create a block map somehow, e.g., a 2d boolean array of values representing the girds availability (free or not).

Then loop through all the objects in your Level that represents a wall of some kind (that prevents movement through it). For each of these objects, set the gird values that they touch (based on their position, size and rotation) to blocked.

 1  2  3  4  5  6  7  8  9 `int gridSize = 8;int w = level.width / gridSize;int h = level.height / gridSize;boolean[][] blockMap = new boolean[w][h]for (Object o : level.gameObjects) {  if (!o instanceof Wall) continue;  Wall wall = (Wall) o;  wall.addToBlockMap( blockMap, gridSize );}`

The basic (non-rotated) Wall object could look something like this:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 `int w = 20;int h = 10;int x = 12; // x-position in levelint y = 9; // y-position in levelpublic void addToBlockMap( boolean[][] map, int gridSize ) {  int gx = this.x / gridSize; // calculate position in grid  int gy = this.y / gridSize;  int gw = this.w / gridSize; // calculate size in grid  int gh = this.h / gridSize;  for (int i = 0; i < gw; i++) {    for (int j = 0; j < gh; j++) {       map[gx + i][gy + j] = false; // not free    }  }}`

 Games published by our own members! Check 'em out!
CommanderKeith
 « Reply #10 - Posted 2014-03-15 10:29:50 »

Hi, I made a little project that might help with non-tile-based pathfinding:
Cheers,
Keith

princec

« JGO Spiffy Duke »

Medals: 1033
Projects: 3
Exp: 20 years

Eh? Who? What? ... Me?

 « Reply #11 - Posted 2014-03-15 17:34:12 »

A* isn't restricted to grid topologies. You can have any topology you like in there.

Cas

jonjava
 « Reply #12 - Posted 2014-03-15 19:39:53 »

Sure but does anything else make sense for a top down game?

princec

« JGO Spiffy Duke »

Medals: 1033
Projects: 3
Exp: 20 years

Eh? Who? What? ... Me?

 « Reply #13 - Posted 2014-03-15 19:58:48 »

Well, just sayin'. OP specifically points out that it's not a tile-based grid map. Maybe he could be using space partitioning trees and the centrepoints of leaves as the topology.

Cas

trollwarrior1
 « Reply #14 - Posted 2014-03-15 20:00:53 »

A* isn't tile based algorithm. It is node based. You can place nodes where ever you wish.. Computers have like no limits to what you can do other than computing power..
Roquen

JGO Kernel

Medals: 517

 « Reply #15 - Posted 2014-03-15 20:53:31 »

The short answer is there are lots of options.  Try searching for "any angle pathfinding".
Opiop
 « Reply #16 - Posted 2014-03-16 00:25:50 »

He asked for a simple implementation, that's why I recommended tile based maps. I know it isn't restricted to tiles.
Roquen

JGO Kernel

Medals: 517

 « Reply #17 - Posted 2014-03-16 12:34:41 »

Ughh.  I did the search I suggested and wasted a bunch of time looking at stuff developed since the last time I looked.  Jump point search looks like it might be interesting.  Now...I don't need any pathfinding...I don't need any pathfinding....
Roquen

JGO Kernel

Medals: 517

 « Reply #18 - Posted 2014-03-16 12:36:56 »

...Oh and some picture comparisons of some various mods

http://harablog.wordpress.com/2011/09/07/jump-point-search/

I'm stopping now.
SHC
 « Reply #19 - Posted 2014-03-16 13:00:00 »

Amit's Game Programming Information has some nice notes on A* pathfinding algorithm here.

http://theory.stanford.edu/~amitp/GameProgramming/

Gibbo3771

JGO Kernel

Medals: 128
Projects: 5
Exp: 1 year

Currently inactive on forums :(

 « Reply #20 - Posted 2014-03-16 13:05:16 »

Amit's Game Programming Information has some nice notes on A* pathfinding algorithm here.

http://theory.stanford.edu/~amitp/GameProgramming/

What a page btw, very good information.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
FewCode

Senior Newbie

Medals: 1
Exp: 3 years

 « Reply #21 - Posted 2014-03-17 03:21:28 »

Thanks for the help so far everyone.

Now for an update

So I had a bit of time and implemented A* into the game as well as what jonjava said about converting it into a grid.

Here is my result:

No, it works... mostly. its not that optimized, but I still have lots of work for that and I am getting there.

my problems that I have encountered are:

1. They do not handle corners very well.
• If the object that needs the path-finding is bigger then a tile, it might actually get stuck on a wall. So far, I can get around that with rotated collision detection. but this would be temporary as I will have bigger objects that need pathfinding later. So, I am not sure what to do in that sense. I will have more of a look later, I think someone was asking about the same issue on this forum.

2. their paths are wonky
• As you can see in the image, the blue square down the bottom left of the image is actually going to go up before it goes down. This is something that popped up and I'm not sure whats wrong. It will most likely be due to some bad math on my part, but still annoying anyway.

3. The objects on the grid
• Because of the way that the objects are being converted on the grid, you can see that both the (badly drawn) mines and the (badly drawn) boxes do not appear as blocked correctly. now again, this is probably due to some bad math on my part. but, lets get down to the root of this problem:

My tile's size is 16x16. so, if an object, much like those boxes, were not constrained to that relative size, it would create problems. those boxes are actually 30x30 pixels, close but not the same as 2x2 tiles. You might be able to see that later I could have a quite a lot of objects that are not contained by the tile's relative size. this might create wonky pathfinding and places where the pathfinding algorithm cant see a path, but to the user there clearly is one (between two objects).

So, those are my problems that have arisen so far.

I will have a look at the suggestions and resources that you all sent me and see if i can improve it a lot more (I most likely can)

Also, just a side note, the map sizes themselves are multiplies of 50, from 100 all the way up to 500 (e.g. 100, 150, 200, 250...). so, i'm guessing this could get quite taxing when a lot of objects are on screen at once.

Thanks again for the help
p.s. I have been programming so much lately that it was so hard not to put a semicolon on the end of each line...
Gibbo3771

JGO Kernel

Medals: 128
Projects: 5
Exp: 1 year

Currently inactive on forums :(

 « Reply #22 - Posted 2014-03-17 11:10:59 »

I have implemented A* into my game as well and have the same wonky path pattern, I am not sure why it does it. It only does it if I allow diagonal movement (which I sort of want).

It got better when I changed the heuristic calculation from:

 1  2  3  4  5  6  7 `   public float getEstimatedDistanceToDest(int startX, int startY, int destX,         int destY) {      float dx = destX - startX;      float dy = destY - startY;      return (dx + dx) * (dy + dy);   }`

To:

 1  2  3  4  5  6  7 `   public float getEstimatedDistanceToDest(int startX, int startY, int destX,         int destY) {      float dx = destX - startX;      float dy = destY - startY;      return (float) Math.sqrt((dx+dx)*(dy+dy));   }`

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
VIrtueeL
 « Reply #23 - Posted 2014-03-17 11:34:32 »

use vector2F and make 1 with move and one moveto

then check if the ais pos < then the target

works for me =D

i do devlogs and i do tutorials check em out
Opiop
 « Reply #24 - Posted 2014-03-17 12:10:59 »

Yeah that was so helpful, thank you for that.
FewCode

Senior Newbie

Medals: 1
Exp: 3 years

 « Reply #25 - Posted 2014-03-18 05:25:29 »

Ok, i fixed my problem with number 2. It was a very silly problem, just me overlooking data values.

It was some a conversion problem. they were using ints instead of floats for the pathing calculation. While I would rather ints (whole numbers are fun ) it was actually cutting off the decimal that I got from my calculations.

My calculations look very much like what Gibbo had. so, imagine ints where the floats are.

Hint for future people looking into A* pathing: Don't use ints unless your calculations result in whole numbers.
Gibbo3771

JGO Kernel

Medals: 128
Projects: 5
Exp: 1 year

Currently inactive on forums :(

 « Reply #26 - Posted 2014-03-18 09:00:33 »

Switching to floats right now... Never even thought of that

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
dezzroy

Senior Newbie

Exp: 10 years

 « Reply #27 - Posted 2014-03-25 10:05:34 »

Hi, FewCode, are you still working on this? I have a working solution for almost exactly this situation.

I don't use tiles. I use nodes which are generally located around the corners of the walls. I found this to work nicely and avoid the issue your image shows with the odd paths.

I assume by now you are familiar with implementing the A* algorithm, given that image and the content of your last posts.

Basically, in my system, the world has positive space (can be traveled through, like your gray areas) and negative space (can not be traveled through, like your walls).
The nodes are generated as follows:
• For each positive space, generate nodes near the corners, and on the inside of the positive space.
• For each negative space, generate nodes near the corners, and on the outside of the negative space.
• If a node ends up being too close to any negative space (or in it), ignore it during the pathfinding process, or delete it. (the closeness is an issue if you don't allow your characters to intersect negative spaces at all)
• Generate a beginning node for the character's current position, and a destination node for the destination.

I use rectangles for negative and positive spaces, but I think as long as the spaces are convex polygons (such as a rectangle), the system stays reasonably simple.

On a side note, my characters are strictly not permitted to intersect any negative space, which brings up an issue of how far away nodes should be from the corners (vertices) of positive and negative spaces. I have a policy in place that addresses this, but this may be irrelevant for you, so I'll refrain from describing it in this post.

Let me know if you have any questions or interest in knowing more about the solution I use. By the way, I am curious if you allow your characters to rotate and translate freely, given your system is not tile-based.

Pages: [1]
 ignore  |  Print

 EgonOlsen (78 views) 2018-06-10 19:43:48 EgonOlsen (58 views) 2018-06-10 19:43:44 EgonOlsen (78 views) 2018-06-10 19:43:20 DesertCoockie (260 views) 2018-05-13 18:23:11 nelsongames (158 views) 2018-04-24 18:15:36 nelsongames (157 views) 2018-04-24 18:14:32 ivj94 (898 views) 2018-03-24 14:47:39 ivj94 (162 views) 2018-03-24 14:46:31 ivj94 (811 views) 2018-03-24 14:43:53 Solater (175 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 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