Jump to content
  • Advertisement
Sign in to follow this  
mousetail

Slow performance on A*

This topic is 1435 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)
        weightsgrid[pointa]=1
        tries=0
        while weightsgrid[pointb]==-1 and tries<100:
            tries+=1
            for coords in weightsgrid:
                if weightsgrid[coords]>=-1:
                    posible=[]
                    if weightsgrid[coords]!=-1:
                        posible.append(weightsgrid[coords])
                    for adj in getadjacent(coords):
                        try:
                            if weightsgrid[adj]>0:
                                posible.append(weightsgrid[adj]+max(weights[self[adj]],weights[self[coords]]))
                                #print "Did SOmething"
                            else:
                                pass
                        except IndexError:
                            pass
                            #Can forget about this error since we don't care about values outside the grid
                    if len(posible)>0:
                        weightsgrid[coords]=min(posible)
        
        walkposition=tuple(pointb)
        l=None
        tries=0
        if not function:
            l=[]
            function=l.append
        while walkposition!=tuple(pointa) and tries<len(self.data):
            try:
                walkposition=min(getadjacent(walkposition),
                             key=lambda x: weightsgrid[x] if weightsgrid[x]!=-1 else 8388608)
            except IndexError:
                print walkposition
            #weightsgrid[walkposition]=8388608
            function(walkposition)
            tries+=1
            #print tries
        self.weightsgrid=weightsgrid
        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:

        numrooms=len(self.data)//512
        rooms=[]
        print "0}GENERATING ROOMS"
        for i in range(numrooms):
            ok=False
            tries=0
            while not ok:
                x=random.randint(10,self.rowsize-19)
                y=random.randint(10,len(self.data)/self.rowsize-19)
                width=random.randint(8,16)
                height=random.randint(8,16)
                floormats=random.choice([(3,4),(5,6)])
                room=[x,y,width,height,floormats,Storage_Obj()]
                ok=True
                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
                        (room2[1]<room[1]+room[3]+3)):
                        #print room,room2
                        ok=False
                if not ok:
                    tries+=1
                    #print "tries: ",tries
                if tries>1000:
                    print "failed after",tries,"tries"
                    break
            if tries<=1000:
                rooms.append(room)
        
        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):
                    ok=False
                    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):
                            self[i,j]=random.choice([1,1,1,1,1,2])
                        else:
                            self[i,j]=random.choice(room[4])
                        ok=True
        print "0}Connecting rooms!"
        timesperroom=1
        totaltimes=timesperroom*len(rooms)
        timestried=0
        lasttime=datetime.datetime.now()
        for room1 in rooms:
            room2s=[random.choice(rooms) for i in range(timesperroom)]
            for room2 in room2s:
                if room1!=room2:
                    timestried+=1
                    center1=room1[0]+room1[2]//2,room1[1]+room1[3]//2
                    center2=room2[0]+room2[2]//2,room2[1]+room2[3]//2
                    #try:
                    print "Running a*! ({0:0>2}/{1:>2}) time: {2}".format(timestried,totaltimes,datetime.datetime.now()-lasttime)
                    lasttime=datetime.datetime.now()
                    self.astar

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

[attachment=24235:gamedev1.png]

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

[attachment=24236:gamedev2.png]

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

Edited by mousetail

Share this post


Link to post
Share on other sites
Advertisement

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
My Python isn't terrific, but I'm having a hard time understanding how your code is an implementation of A*?

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.
 

100*weightsgrid.size*getadjacent

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
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!