# 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.

## 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])
try:
#print "Did SOmething"
else:
pass
except IndexError:
pass
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:
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 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 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 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 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 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 on other sites

I edited the post with a few screen shots, since I see you don't get my problem

##### 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.

1. 1
2. 2
3. 3
Rutin
18
4. 4
JoeJ
14
5. 5

• 14
• 10
• 23
• 9
• 32
• ### Forum Statistics

• Total Topics
632630
• Total Posts
3007525
• ### Who's Online (See full list)

There are no registered users currently online

×