Square grid, turn base A.I.

I needed a A.I. to navigate some monsters in a turn base game I’m making. I couldn’t think of a way to use pandAI, so I made my own AI.

Don’t expect too much, the AI is about 30 lines of code so from time to time it can act really stupid, but in most cases it can still find it’s way.

I’ve made a small demo to demonstrate:

RJqGO.jpg867×706

It’s a bit messy and if you press the space while the rat is moving it all goes wrong, but apart from that I think it’s quite an entertaining demo.

Download link:
sendspace.com/file/xtpehw

WTFPL license. Have fun

Are you talking about a “Path Finding” type AI? or a “Move To Point?”

It’s just a ‘move to point’, there’s no real pathfinding. The simplest thing that could work.

I see. I usually just use vector math for that kind of thing. Works like a charm.

How would I use vectors to avoid blocked tiles?
In this code I’m making a list of all (4) moves, then I filter the list for blocked tiles, moves that move away from my target and visited tiles. If the last two filters give a empty list I drop that filter. Finaly I pick one tile at random from the filtered list.
If there’s a simpler way to do this with mathemagic vectors then hell yes, can I have one?

One textbook approach I would have used is defining a “score” that represents the number of squares something is from the target. Then the goal is to minimize that score (it will be able to reach zero as long as there is some path).

In this case I’d probably use depth-first search to do the actual grunt work. The whole thing could be written in very few lines of code and guarantee a perfect solution every time (assuming there is a solution).

Disclaimer: I have not examined PandaAI whatsoever. This was just some stuff from a university AI course.

I have no formal education in programming and terms like ‘depth-first search’ scare me (I had to look it up in wikipedia just to know what it is).

This is just my gut feeling that searching for the perfect path in a turn based game is kind of wasteful. There’s a big chance that the AI will not reach the goal in this turn and in the next turn the searching for a path will start from zero because the target moved.

How can I check the ‘score’? I can’t think of any other way then to just try all the routes… that alone seams like a lot of work. I tired to visualize a simple case, but I’ve run out of colors:

Or is it just about finding any route and end there? I feel, I’m too stupid for all of this.

Here’s the code I’m using:

def ratAI(self):
        xDist=abs(self.targetX-self.ratX)
        yDist=abs(self.targetY-self.ratY) 
        if(xDist==0 and yDist==0): 
            return 'Eat_da_cheez!'
        #all moves    
        moves=[ (self.ratX-1,self.ratY),
                (self.ratX+1,self.ratY),
                (self.ratX,self.ratY-1),
                (self.ratX,self.ratY+1)]
        
        #check if tiles are on map
        moves=filter((lambda move: move[0]>-1 and move[1]>-1), moves)
        moves=filter((lambda move: move[0]<10 and move[1]<10), moves)

        #check if tiles are free
        moves=filter((lambda move: self.map[move[0]][move[1]]==0), moves)
        
        #don't visit the tiles 2x       
        filteredMoves=filter((lambda move: not move in self.ratMemory), moves)
        #moves that make sense          
        finalMoves=filter((lambda move: abs(self.targetX-move[0])<xDist or abs(self.targetY-move[1])<yDist), filteredMoves)

        #no finalMoves? drop to filteredMoves
        if( not finalMoves):
            finalMoves=filteredMoves       
        #no filteredMoves? drop to all valid moves        
        if( not finalMoves):
            finalMoves=moves
            
        #select just one    
        finalMoves=random.sample(finalMoves, 1)        
        #save for later
        self.ratMemory.append(finalMoves[0])
        self.ratX=finalMoves[0][0]
        self.ratY=finalMoves[0][1]
        #failsafe
        if(len(self.ratMemory)>80):
            self.ratMemory=[(0,0)]
        return finalMoves

I run it one per frame as long as my ‘rat’ has ‘action points’. I’ll welcome any improvements (even if I don’t understand them).

True, it would be searching theough every single possible path, although not if the score could be estimated with a heuristic of some sort. There’s an example I just found of the A* method. Probably overkill, though, since the method you have works - I was only mentioning an alternate approach.

Technically, finding the shortest possible path is not always desirable. Game AI got everyone used to this, but it results in predictable and unrealistic behavior.

Then you are doing something similar to “Path Finding.” That’s why I asked the question I asked. Since you said “Move To Point”, I assumed you wasn’t avoiding anything.

I have implemented my own “Path Finding” and “Move To Point” code. However, giving the game you are making, my code would probably not fit within your code style.

PS,

I do use Vectors even with my “Path Finding.” Works like a charm.

I didn’t want it to seem like I was intruding on a thread and not giving any suggestions, so may I share an idea with you?

Keep in mind, there are many ways to approach the same problem in programming. What I’m going to share is just the easiest way I could think of right off the top of my brain.

I’m assuming you want to move the Rat (mouse) from tile to tile, while avoiding any tile that has something on it until the Rat reaches a goal? Correct?

What I would probably try first is “nested dictionaries.” I’m assuming you’re familiar with Python Dictionaries. I would write the “Path Finding” AI for this type of game as follows –

By markjacksonguy at 2012-03-07

Lets say the Rat is starting on block A. I would find the current key in my Dictionary, which is the current block the Rat is over (A), and then I would find the connected keys (which are all the blocks that sit around the block the Rat is on. E.g. B, C, D).

I would then check to see if anything is on any of the blocks around the block the Rat is on (by using a variable or something). Once I have determined all the free blocks (empty blocks), I would then perform a distance to point check using Vector Math on each free block to determine which distance is shortest. I would then move the Rat to the block that has the shortest distance; and then repeat the process until the Rat reaches goal.

Of course, if I had the time, I could write this code since it’s not that hard. I hope I at least gave you some ideas.

In the RTS style game I’m making, my characters do not move by grid; they move freely, that’s why I would have to write something like the example above if I was going to use a grid base movement approach.

Update-------------------------
I thought about it a little more and the approach would be to use lists and a dictionaries together. Each block is a Key and the Value is a list containing the blocks around the current block the Rat is on. I almost want to take time out from my work and write a demo since it’s so simple.

The cool thing about this approach is the fact you’re not checking every possible path (that would be many); you are in fact performing movement checks block to block, at the same time finding the shortest path (if that’s what you desire).

Now I’m getting excited about grid base movement.