Finding empty places

Game Engine Game Engine Support and Discussion
1

Hello
I’m thinking about doing a turned based action game, a bit like the battles in Heroes of might and magic. But probably sci-fi.

Anyway:
I think I can pull of a decent pathfinding script that will suit my needs, if I can get help on this one:
Is there any smart way of finding out if there is something at a certain spot or not?
I thought about rayCasting from above and see if I hit anything but the ground, but is there a better way? Objects can be big and have odd shapes so just comparing their positions won’t do.

2

So your trying to find if something is blocking your path?
Maybe everytime the player reaches a new node it casts a ray to the next one to see if its clear.

I’m not so sure what you’re asking, but I think rays are what you need to do unless its tile based.

3

Okey, well something like this:
http://images.macworld.com/images/legacy/2007/09/images/content/hommv.jpg I will not have a visible grid, I just want to be able to tell if a unit can reach a certain square in their turn, so if you hover your mouse over a square it will either turn red (if you can’t reach it) or green and highlight the path (if you can reach it).

My plan was to:

  1. check if the goal is within the maximum walking distance with no obstacle
  2. collect all obstacles
  3. find the path.

I’m stuck at number two, I have an idea how I will solve 3 (I’ve been reading and collecting posted blend files)

4

Well, you can create a two dimensional list for storing passable tiles:

passable_tiles = []
width = 10
height = 10
for x in range width:
    passable_tiles.append([])
    for y in range height:
        passable_tiles[x].append(1)

Then as a unit moves onto that tile you set it to impassable:

pos = unit.getPosition()
x = int(round(pos[0],0))
y = int(round(pos[1],0))

passable_tiles[x][y] = 0

Something like that. That passable_tiles list will be essential to the path finding as well.

If you want I can give you the pathfinding file for pit monsters, it should be easy for you to as they’re both tile based.

5

Thanks for the advice, but for things like terrain or such, when the object is bigger than a tile how would I go about that? (a river or a big rock or wall) I could manually type all the impassable tile for every map but I hoped to write a script that could find that out at start-up.

I would gladly take a look at your script.

And now I will be going on a short trip, this thread might be revived at Wednesday or Thursday.

6

Here is the pathfinding script with a demo. Its based on the pseudo code from:

To run it save it somewhere, open it up, open the pathfinding.py text file and then save it as pathfinding.py in the same directory as the .blend. Re open the .blend and play it.

Click on a tile to see the path there.

It works like this:

path = GameLogic.pathfinding.getPath(start, goal, passable_tiles)

start is a list: [x,y]
goal is a list: [x,y]
passable_tiles is a two dimensional list that represents the grid, 1 is passable, 0 is impassable: [ [1,1,1,1], [ 1,1,1,1], [1,1,1,1], [1,1,1,1] ] is a 4 by 4 grid, all passable. You can get a single tile with:

passable = passable_tiles[x][y]
if passable == 1: ect

Thats pretty much it, the init script puts the pathfinding module on GameLogic, creates the passable_tiles list and shows the mouse. The update script finds a path when the lmb is pressed and draws it on the grid.

The pathfinding script is pretty nooby (as it was my second attempt at pathfinding), but I guess its allright. It does not take into account a cost system (deters the path from going over a tile), but you don’t have to worry about that I guess.

Attachments

tile_pathfinding.blend (145 KB)

7

Ooohhh…i love Heroes of Might And Magic… I want to see this game being made! :slight_smile:

/Radman

8

andrew-101:
Thank you very much. I’ll try to make it work the way I want it to.

Radmanlive:
I’ll do my best, but don’t get your hopes up yet.