FewCode
Junior Newbie  Exp: 3 years
|
 |
«
Posted
2014-03-15 01: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 02: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
Junior Newbie Exp: 3 years
|
|
«
Reply #2 - Posted
2014-03-15 02: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!
|
|
|
opiop65
|
|
«
Reply #3 - Posted
2014-03-15 02:39:48 » |
|
You're going to need to split your map up into a grid anyway. That's how basic A* works.
|
|
|
|
FewCode
Junior Newbie Exp: 3 years
|
|
«
Reply #4 - Posted
2014-03-15 02: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.
|
|
|
|
|
|
opiop65
|
|
«
Reply #5 - Posted
2014-03-15 02: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
Junior Newbie Exp: 3 years
|
|
«
Reply #6 - Posted
2014-03-15 02:47:05 » |
|
Its more of, i don't know how to implement it in my game.
|
|
|
|
|
|
opiop65
|
|
«
Reply #7 - Posted
2014-03-15 02: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
Junior Newbie Exp: 3 years
|
|
«
Reply #8 - Posted
2014-03-15 02: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 04: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; int y = 9; public void addToBlockMap( boolean[][] map, int gridSize ) {
int gx = this.x / gridSize; int gy = this.y / gridSize;
int gw = this.w / gridSize; 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; }
}
} |
|
|
|
|
Games published by our own members! Check 'em out!
|
|
|
|
|
princec
|
|
«
Reply #11 - Posted
2014-03-15 18: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 20:39:53 » |
|
Sure but does anything else make sense for a top down game?
|
|
|
|
|
princec
|
|
«
Reply #13 - Posted
2014-03-15 20: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 21: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
|
|
«
Reply #15 - Posted
2014-03-15 21:53:31 » |
|
The short answer is there are lots of options. Try searching for "any angle pathfinding".
|
|
|
|
|
|
opiop65
|
|
«
Reply #16 - Posted
2014-03-16 01: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
|
|
«
Reply #17 - Posted
2014-03-16 13: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....
|
|
|
|
|
|
|
|
|
|
Gibbo3771
|
|
«
Reply #20 - Posted
2014-03-16 14:05:16 » |
|
What a page btw, very good information. |
"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever |
|
|
FewCode
Junior Newbie Exp: 3 years
|
|
«
Reply #21 - Posted
2014-03-17 04: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
|
|
«
Reply #22 - Posted
2014-03-17 12: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 12: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
|
|
|
|
|
|
opiop65
|
|
«
Reply #24 - Posted
2014-03-17 13:10:59 » |
|
Yeah that was so helpful, thank you for that.
|
|
|
|
FewCode
Junior Newbie Exp: 3 years
|
|
«
Reply #25 - Posted
2014-03-18 06: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
|
|
«
Reply #26 - Posted
2014-03-18 10: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 11: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. |
|
|
|
|
|
