AI Script for Existence - Problem

New problem, check last post.


---------------[original post]-------------------------------------------------------
Well, after doing the LOD script, I decided to keep on going and code what was left with the game. Next on the list was Ai.

Description is on the script, but basically it is a master script for 3 different types of animals Passive, Neutral, Aggressive.

Change the type property to change the type of animal.

As usual please critic and give your suggestions to make this more realistic.


AI.blend (163 KB)AI Better example.blend (174 KB)

I think that all the predators should stop chasing you at some point, even if you need to hide behind something they can’t pass or something to do it. Perhaps add a timer property which tells your script how long its been since “nearestEnemy” has been seen within the radar cone.

A radar cone, though simple, may not be the method you want to use, since it can see through objects (where as tigers can’t). Look into using the RayCastTo or RayCast methods to detect whether an object is hidden from the enemy (even if they are close together).

Also, all of your characters need to be somewhat physics-enabled (even if its totally faked) so they don’t pass through walls or other characters. A simple ray sensor could stop them from moving forward into a wall, and using the gethitnormal method, might be able to figure out which way is the easiest to turn. That’s not all “intelligent”, though.


Your right, this script is not Existence worthy:no: So, I put in A* pathfinding:yes: (thanks to chaser) I modified chaser’s scripts, and used mine as the control script. It was the longest 10 hours of my life getting this to work… and it still has some glitches, but for the most part, it works.

You can still change what kind of aggressiveness you want by changing the ‘type’ property.

Here are the different types:

Passive - Will run away if you hurt it
Neutral - Will attack only if you hurt it
Aggressive - Will attack you on sight

Currently it supports:

Multiple bots
tracking to player


Individual tracking
track to anyone that poses a threat.

Sorry if I missed anything, I am very rushed right now.

This is still a very WIP. Any comments on the script, is very welcome.

Space - add an AI
right ctrl - hurt the AI


AI Pathfinding.blend (670 KB)

Wow, your pathfinding runs at 6fps with only 4 objects on my computer ^^ And the fps reduces more and more as time goes on. And the objects sometimes walk in small circles, something is going wrong there.

I took a quick look at your code and you could optimize it a lot. I’d use a much more linear programming instead. Sacrifice readability for performance.

I also noticed your code is too generic. For a maze like that you don’t have much use for A*'s heuristics, you don’t have much info to use for heuristics that would slow you down. Should just use Dijkstra’s instead. It’s also too generic on the nodes connections, you have some big nodes there, that your game might not need. Maybe you could just limit that to cut down the search. You could also just limit it to equidistant nodes (ex. squared tiles) and remove all the distance calculations. Seems like you’re wasting too much processing with that when all your nodes have almost the same distance anyway.

The beauty of A* is that you get a fast calculation when you only have some very irregular waypoints and you have some information about each path’s speed to use in heuristics. You don’t have either so you’re wasting processing by using A*. Should just aim for something simple that fits your specific needs, not a generic purpose A*.

Tho I didn’t really study your code and don’t know what heuristics you’re using, if any. But it’s definitely very slow.

Um, thats strange, you sure its not from the graphics? I get 50-60fps with 4 bots.

I agree that the code needs to be cleaned a lot, and I am currently doing that, I also need to stress that the base of this isn’t my code. It came from here. I modified it, so I could have multiple instances of it (although it is a little glitchy at the moment) and so it follow the player, instead of a mouse click.

If anyone has done this before, I would love to take look at their code. Pretty please.

attached is a screen with 4 bots at the same time, along with an updated blend.


AI Pathfinding update 01.blend (683 KB)

Yep, maybe you should check your driver vibrunazo. My current laptop gives me 16 fps even with its crappy intel card.

I download your previous .blend -> open it -> click to show framerate and profile -> press P -> space 4 times -> framerate quickly goes down to 5~6, framerate debug says: logic 30ms (40%, which is VERY high) Once it gets to the end it locks up at logic > 90%. So it’s something in the code, not the rasterizer.

I tried your newest .blend. Pressed P, couldn’t add new objects with spacebar. A single object walks to the middle with 30fps (max on my system). Then as he gets close to the middle it gets slow and slower until it locks up at logic > 90%.

I guess that it’s something wrong to the code you added to try to get the player? Should double check that.

Anyway I’ve been toying with different pathfinding algorithms this week. So far my best one works on a tiled map (4 side equidistant nodes), it works pretty fast (it’s similar to Dijkstra but without distance and node size check) but it doesn’t walk on diagonals. Which is pretty ugly. I already made a separate code to optimize the path found to diagonals now it’s just a matter of putting them together. But I proly won’t have time this weekend. I’ll show it to you once I got it to a satisfying state.

Thats weird, I hope I can find whats causing that.

I founded out the lock up problem and fixed it. (at least its fixed as long as you stay on the node mesh)

I also cleaned up a lot of the script. And I think its a bit faster.

Multiple bots doesn’t work anymore(my bad) so I am going to try and fix that.

An updated blend:


AI Pathfinding clean.blend (679 KB)

Haha. 2 minutes after I posted I fixed the multiple bots support.

There are no bugs as far as I can tell. (thats your job community!)

Things I need to add:

Different destinations for the different bots.

Almost done!


AI Pathfinding updated 02.blend (690 KB)

nice path finder.

any idea on how to make a path finder without the use of nodes ?

…maybe not if you’re using this technique,

but I’d still lov to know if there’s one…

again, nice script :yes:

I’m not sure if there is one that bypasses nodes, but I bet there is somewhere in the internet. A* uses nodes.

I think I am done with this. I might add the multiple destinations later, but I have a question.

Is there a way to delete faces without deleting the edges around them, or convert a face into edges?

EDIT: Never mind I found a way. In edit mode, go to scripts and select the script solidwireframe, and tweak with the settings. It will create a edge only version of the mesh(landscape)

Thats chaser’s A* demo, which doesn’t uses a sort of hybrid nav-mesh/nodes system. It starts with a mesh, then breaks it down into nodes at each vertex.

@Excalaberr, to delete only faces select the face, press del or x, then delete faces only. It should leave the edges.

Okay, I though I had this done enough, but when I moved this to my Main game, I got the freeze glitch again. I spent about 2 days trying to fix it, but I dont really know whats causing it.

Any help would be gratefully received!


Pathfinding reworked.blend (721 KB)

Okay, I am finally not rushed right now! Nice and calm, and able to give explanations! :slight_smile:

Anyway, I reduced the amount of scripts from 5 to 3. I merged 3 of the scripts into 1, which is the main AI script, then there is the and the I am also looking into implementing binary heaps, as that will increase the speed. The speed right now is manageable, it takes 3-4 fps to update, and it updates every few seconds, so its not bad, except the freeze problem…

On the freeze problem, I figured out what is causing it! It happens when it looks for a path and cannot find one. The problem is under the script. The fps drops about 100 for around 1 second, which if you’re running it on a game that runs at a normal 30 fps…

Anyone have any ideas on how to fix it? I am at a standstill from this problem. Any experienced python coders feel nice?

I started learning python about 1 month ago, so I enjoyed trying to figure this out, but it reached the end of its excitement.

oh, and btw thanks for the tip andrew-101!

I attached the problem code, and the blend. I removed the AI functions from the AI script, so its just pathfinding.

EDIT: I might have attached the wrong blend… :o

EDIT: I think the problem lay in line 157 - 170. I also posted the code in for easier viewing.

### ------ Pathfinding ------ ###
### Copyright 2009 Chase Moskal!
# This contains the PATHFINDER class,
# which contains classes for NODE and PATH.
# It's for A* pathfinding.

INIT = 0

    import math

    class NODE:
        def __init__(self, PATHFINDER, position, adjacentpos):
            self.PATHFINDER = PATHFINDER

            self.position = position
            self.adjacentpos = adjacentpos
            self.parent = None
            self.adjacent = []
            self.G = 0
            self.H = 0
            self.F = 0

        def fastEvaluate(self, startNode, targetNode):
            PATHFINDER = self.PATHFINDER
            G = PATHFINDER.getManhattanDistance(startNode.position, self.position)
            H = PATHFINDER.getManhattanDistance(self.position, targetNode.position)
            F = G+H
            self.G = G
            self.H = H
            self.F = F
            return F, G, H        
    class PATH:
        def __init__(self, startpos, targetpos, startNode, targetNode, OPEN, CLOSED):
            self.OPEN = OPEN
            self.CLOSED = CLOSED

            self.startpos = startpos
            self.targetpos = targetpos
            self.nodes = []
            node = targetNode
            run = 1
            while run == 1:
                if node.parent:
                    node = node.parent
                    run = 0
            self.path = self.getPath()
        def getPath(self):
            path = []
            for node in self.nodes:
            return path

    # Compiles the adjacents for each node in a list.
    def compileAdjacents(self, nodes):
        for node in nodes:
            adjacent = []
            for targetnode in nodes:
                if targetnode.position in node.adjacentpos:
            node.adjacent = adjacent            

        # Evaluates vertinfolist from string form. 
    def stringToNodemesh(self, string):
        # Converting to unix flavor...
        string = string.replace("
", "

        nodemesh = []
        lines = string.split("
        for line in lines:
            if line:
                    vertinfo = eval(line)

        return nodemesh

    # Takes in a vertinfolist and converts it into a list of node objects
    def NodemeshToNodes(self, nodemesh):
        nodes = []
        for vertinfo in nodemesh:
            position = vertinfo[0]
            adjacentpos = vertinfo[1]
            node = self.NODE(self, position, adjacentpos)
        return nodes

    def makeNodes(self, string):
        nodemesh = self.stringToNodemesh(string)
        nodes = self.NodemeshToNodes(nodemesh)
        return nodes

    def cleanNodes(self, nodes):
        for node in nodes:
            node.parent = None
            node.G = 0
            node.H = 0
            node.F = 0

    def getManhattanDistance(self, A, B):
        math = self.math
        X = abs(A[0] - B[0])
        Y = abs(A[1] - B[1])
        Z = abs(A[2] - B[2])
        D = X+Y+Z
        return D

    # Returns the nearest node, given a position and a list of nodes.
    def getNearestNode(self, position, nodes):
        best = []
        for node in nodes:
            if best:
                bestnode = best[0]
                bestdistance = best[1]
                distance = self.getManhattanDistance(position, node.position)
                if distance < bestdistance:
                    best = [node, distance]
                distance = self.getManhattanDistance(position, node.position)
                best = [node, distance]
        return best[0]

    # Returns the node with the best F score: doesn't evaluate F.
    def getBestF(self, nodes):
        best = []
        for node in nodes:
            if best:
                bestnode = best[0]
                bestF = best[1]
                if node.F < bestF:
                    best = [node, node.F]
                best = [node, node.F]
        return best[0]

    ###### ------ fastFindPath ------ ######
    # Given a list of nodes, start position, target position, and
    # max number of steps, this method will return a path object.
    # This will usually find a path faster, but at the expense of accuracy.
    def fastFindPath(self, nodes, start, target, steps=200):
        PATHFOUND = 0

        startNode = self.getNearestNode(start, nodes)
        targetNode = self.getNearestNode(target, nodes)

        OPEN = [startNode]
        CLOSED = []

        for i in range(steps):

            # Get node in OPEN with lowest F
            currentNode = self.getBestF(OPEN)

            # Switch it to CLOSED

            # For each adjacent node
            adjacentNodes = currentNode.adjacent
            for node in adjacentNodes:

                # If it's not in CLOSED
                if not (node in CLOSED):
                    # Get F Score
                    F, G, H = node.fastEvaluate(startNode, targetNode)

                    if not (node in OPEN):
                        node.parent = currentNode
                        if node.G < currentNode.G:
                            # No change to parent, and already in the OPEN list.
                            node.parent = currentNode

            # Stop when we found the target node or if there are no more open nodes.
            if targetNode in OPEN:
                targetNode.parent = currentNode
                PATHFOUND = 1
            if not OPEN:

        if PATHFOUND:
            path = self.PATH(start, target, startNode, targetNode, OPEN, CLOSED)
            return path
            return 0

Pathfinder = PATHFINDER


AStar Pathfinding.blend (273 KB)

Triple post! :no:

Anyway, as I edited above, I posted the wrong blend file, and I think the problem lays in lines 157 - 170, that part is supposed to find the node with the lowest F value, I think it is running more than once, and I also think that is where a lot of the performance is lost.

Is the problem that the bot doesn’t reach the last node?

I think the problem lies in AI Updated line 99, change the 15 to something alot smaller, like 1 and the bot will go all the way to the end.

@ Andrew, unfortunately that isn’t the problem.

Okay, more on the problem.

It defenitly happens on the part that returns the node with the best F score, which is lines 156-170. It is only supposed to update once, but it keeps updating. I also found out that this happens in the chaser demo too, so it isn’t some mistake I made converting the code.

Look at the attached pic. The console on the right is when there is a node between the player and the bot, on the left, there isn’t. See the difference. It is updating way to often.


According to the script, you seem to be returning best in line 169 for each node in your node list. Shouldn’t it only be returned once?