AI path finding on non tile based game?

Game Mechanics Artificial Intelligence
#1

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. :slight_smile:

#2

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.

#3

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.

#4

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

#5

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.

#6

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

#7

Its more of, i don’t know how to implement it in my game.

#8

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

#9

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.

#10

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.


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:


int w = 20;
int h = 10;
int x = 12; // x-position in level
int y = 9; // y-position in level
public 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
    }
  }
}
#11

Hi, I made a little project that might help with non-tile-based pathfinding:
https://code.google.com/p/straightedge/
Cheers,
Keith

#12

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

Cas :slight_smile:

#13

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

#14

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 :slight_smile:

#15

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…

#16

The short answer is there are lots of options. Try searching for “any angle pathfinding”.

#17

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

#18

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…

#19

…Oh and some picture comparisons of some various mods

I’m stopping now.

#20

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

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