• Advertisement
Sign in to follow this  

Slow performance on A*

This topic is 1251 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For my level generator, I need to connect my rooms with passageways. I don't want pasageways to run straight thew other rooms, or crash straight allong walls, turning a whole row into doors, wich looks ugly, so I decided to use a more complicated algorithm to find the path for the paths:

        weightsgrid=Grid([self.rowsize, len(self.data)/self.rowsize],-1)
        while weightsgrid[pointb]==-1 and tries<100:
            for coords in weightsgrid:
                if weightsgrid[coords]>=-1:
                    if weightsgrid[coords]!=-1:
                    for adj in getadjacent(coords):
                            if weightsgrid[adj]>0:
                                #print "Did SOmething"
                        except IndexError:
                            #Can forget about this error since we don't care about values outside the grid
                    if len(posible)>0:
        if not function:
        while walkposition!=tuple(pointa) and tries<len(self.data):
                             key=lambda x: weightsgrid[x] if weightsgrid[x]!=-1 else 8388608)
            except IndexError:
                print walkposition
            #print tries
        return l

note that the class that generates subclasses grid, so self is also a grid object. The function works mostly well, but takes 2 or 3 seconds to run (least is 0.1 second, most is 5 seconds) and since I need to run it 19-38 times each time I generate a level, it becomes kinda unacceptable. Since I am doing this to learn, in the future I might need to use a similar system to for enemy movement, so I want to know what I am doing wrong.
Just in case you need it, this is the rest of my generator function:

        print "0}GENERATING ROOMS"
        for i in range(numrooms):
            while not ok:
                for room2 in rooms:
                    if ((room[0]<room2[0]+room2[2]+3) and #room.right>room2.x and room.x<room2.right
                        (room2[0]<room[0]+room[2]+3) and
                        (room[1]<room2[1]+room2[3]+3) and
                        #print room,room2
                if not ok:
                    #print "tries: ",tries
                if tries>1000:
                    print "failed after",tries,"tries"
            if tries<=1000:
        print "Len(rooms)=",len(rooms)           
            #print [x,y,width,height,floormats]
        print "0}Bordering rooms!"
        for room in rooms:
            for i in range(room[0],room[0]+room[2]+2):
                for j in range(room[1],room[1]+room[3]+2):
                    while not ok:
                        if (i==room[0] or i==room[0]+room[2]+1 or #x position
                            j==room[1] or j==room[1]+room[3]+1):
        print "0}Connecting rooms!"
        for room1 in rooms:
            room2s=[random.choice(rooms) for i in range(timesperroom)]
            for room2 in room2s:
                if room1!=room2:
                    print "Running a*! ({0:0>2}/{1:>2}) time: {2}".format(timestried,totaltimes,datetime.datetime.now()-lasttime)

edit: I see people don't get my problem, so I am going to post a few screen shots to show what I mean:


these are my rooms, but I need to connect them. So I run A* and I get:


this is great, except that it takes 5 minutes to run!

Edited by mousetail

Share this post

Link to post
Share on other sites

Nesting loops will cause an exponential loss in performance and your algorithm is nested three loops deep.


Your worst case scenario is: 100(tries) * weightsgrid.size * getadjacent(coords) = ? some number that is probably pretty big


NO NESTED LOOPS! (unless they’re actually needed)

Share this post

Link to post
Share on other sites
The first loop is to only grow my grid until  I have all the weights between the start point and the end point,
the second loop runs threw all the tiles to see if they have a adjacent tile with a value yet
the third loop runs threw all the adjacent tiles, and selects the smallest one to be the value of the tile. I also evaluate tiles that already have a value again for if a new route from the other direction has been generated.
This is what I understood from the wikipedia entry on A*, but I am not sure if I am doing it correctly. The main difference seems to be that the wikipeda formula checks for a straight line first, but I can't do that because there is allays a straight line, I just want it to avoid walls, but if there is no way to do that, it will just crash threw them. I also want it to be more likely to follow existing pathways part of the way instead of making new ones.
With my earlier simpler method, it would just make a straight line, right threw rooms and sometimes along walls, turning every wall piece into a door, witch looked very ugly.


that is 100*10000*4=4000000 (4M), that is a pretty big number, but every nesting seems to be necessary. This is also only the maximun number, usually it will reach its destination before 100 tries, or neer the edge, getadjacent will only return 3 values, but actually it will be a full 4M most of the time. Edited by mousetail

Share this post

Link to post
Share on other sites

I can't really see how this is A*, but if you want a non-straight line path, why don't you simply set random weights to the cells that are supposed to connect two rooms? That would create a non linear path and would perform as well as a regular A*.

Share this post

Link to post
Share on other sites

Like many here I don't have the time to read all your code. Your question doesn't make sense to me because A* is used for pathfinding (e.g. find the shortest path from point A to point B in an existing level/map), not for level generation. Possibly you could be using A* to check some property about your generated level, but you'd really need to explain more.


If you don't want paths to cross, maybe generate it like a tree, e.g. as you expand your tree forbid touching any other branch. Then as a separate step expand corridors to rooms as desired and add a few loops etc on purpose so the map isn't too predictable.

Share this post

Link to post
Share on other sites

Okay, that makes more sense. Here's some suggestions:

  • I believe that you're trying to join each room with a selection of other random rooms. The problem is that random rooms may be very far away, and the further the distance the larger the area A* will explore. Maybe use a random selection of rooms that are nearby the current room. You could do this a variety of ways, but even the simple option of "Pick X rooms, then filter to the Y closest" may work better.
  • To avoid running along the walls of other rooms, you need some impassable obstacles. Pick X random exit points for each room, then make all the other cells directly adjacent to each room impassable.
  • Are you using an existing implementation of A*? There are many variants which run faster in certain circumstances. See some examples.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement