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:

**gamedev1.png** **74.75KB**
0 downloads

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

**gamedev2.png** **73.96KB**
0 downloads

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