# Finding empty places

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.

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.

Okey, well something like this:
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)

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.

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.

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

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)

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