Basic Grid Base Pathfinding AI

Scripting Issues
1

I noticed Wezu was making a game that involved pathfinding using a grid layout and decided to make a demo that supports my suggestion in the showcase forum.

This code is in no way perfect, because it is not complete! At the same time, it is not flawed either. This demo is of a raw foundation for creating a really good grid base pathfinding AI.

Of course there is more than one way to do it, so someone else might take an entirely different approach. I felt coding it this way would make it really easy for anyone to understand it; plus make it easier to upgrade later.

If anyone does take this code and modify or perfect it into useable code for a commercial quality game, please let me know; I would love to have a copy of that. :slight_smile:

If I had the time, I would do it myself. :cry:

Oh well, knock yourselves out. :smiley:

http://www.freefilehosting.net/pathaigridbase

PS,

I might have typed in some incorrect position values, based on the Blender model file in the data folder. I haven’t found any errors, but if you work on this code and all of a sudden the Rat doesn’t move right, I might have an incorrect center position value for a tile.

I did not leave many notes in the source code, since it pretty much explains itself.

2

Panda3D has grid pathfinding. Why not use that?

3

It sure has better looking models the mine :smiley:

If the tiles would be scaled, and positioned so that the centre of A is at (0,0,0), the centre of B at (1,0,0)… the centre of E at (0, -1, 0) that would make it easer to keep track of where’s where. But that’s not way I’ll stick to my version.

I’ve build a mouse trap and managed to get the mouse stuck:

GTFmj.jpg793×580 

LevelGrid.RatAt = "A";
            LevelGrid.Goal = "D";
            self.Cheese.setPos(4.76, 4.76, 0); 
            self.Rat.setPos(-4.64, 4.68, 0);
            LevelGrid.Blk_Taken = {"A":0, "B":1, "C":1, "D":0, "E":0, "F":0, "G":1, "H":0, "I":0, "J":1, "K":1, "L":0, "M":0, "N":0, "O":0, "P":0};
            LevelGrid.Block1.setPos(-1.49, 4.76, 0); #B
            LevelGrid.Block2.setPos(1.61, 4.76, 0); #C
            LevelGrid.Block3.setPos(1.61, 1.53, 0); #G
            LevelGrid.Block4.setPos(-1.53, -1.61, 0); #J
            LevelGrid.Block5.setPos(1.65, -1.65, 0); #K

I think (no surprisingly) that my code better suits my needs, it dosen’t try to go in diagonal lines, and it already works with ‘action points’ (1 tile long move=1 action point used).

I’ll use the dict for blocked tiles like in your code, a list of lists (sort of 2d array) that I used was a silly idea.

As to why not to use pandAI… I just can’t think of a way to use it for quantized movement… or is there some other hidden grid pathfinding module in panda?

4

The only thing missing from the AI in the Demo is what I like to call “smart AI.” That is, when the obstacles become more complicated, the “Big Rat” would need to know how to deal with tighter situations (not hard to code).

I am keeping this demo in my files so I can return to it in the future and perfect it. The good thing about this kind of grid base pathfinding is the fact you don’t have to create special grid models in some modeling application just to export some special file for pathfinding (navmesh).

If I ever develop games where I need a grid base movement, I will most likely use a completed version of the code in my Demo. The pathfinding coded into my current RTS is completely different from the one in the Demo, so I can pretty much code things lots of ways.

Hell, the grid doesn’t even have to be square with my code because it’s based on points really. It would take some work to set it up for game after game, but I’m thinking about creating (in the future) a finished version that’s a module, so it can be imported into any game, ready to go.

If my grid base pathfinding demo gave someone some code ideas, great, then it served its purpose. :slight_smile:

PS,

Sorry about the Demo’s graphics. I was in a hurry. I created the entire program in maybe… a little over an hour (right before I went to bed)? Something like that. The basic code popped in my head almost instantly.