|
|
|
|
|
|
|
|
Senior Member
Status: Offline
Posts: 577
Join Date: Nov 2008
Location: In the interwebs
|
Jython Pathfinding! -
06-16-2010, 01:35 PM
Here's the code for Jython Pathfinding, after I fixed those horrible bugs!
Code:
map = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
mapstat = false
rows = 0
columns = 0
dictionary = {}
path = []
success = false
def checkmap():
global mapstat,rows,columns,map
if len(map) == 0:
mapstat = false
return
rows = []
for row in map:
rows.append(len(row))
if rows[0] == 0:
mapstat = false
return
rowconform = rows[0]
for lens in rows:
if lens != rowconform:
mapstat = false
return
mapstat = true
rows = len(map)
columns = rowconform
def builddic():
global rows,columns,mapstat,dictionary,map
if mapstat == true:
for row in range(rows):
for column in range(columns):
if map[row][column] == 0:
movements = []
if row > 0:
if map[row-1][column] == 0:
movements.append((row-1,column))
if row < rows-1:
if map[row+1][column] == 0:
movements.append((row+1,column))
if column > 0:
if map[row][column-1] == 0:
movements.append((row,column-1))
if column < columns-1:
if map[row][column+1] == 0:
movements.append((row,column+1))
if row > 0 and column > 0:
if map[row-1][column-1] == 0 and map[row][column-1] == 0 and map[row-1][column] == 0:
movements.append((row-1,column-1))
if row > 0 and column < columns-1:
if map[row-1][column+1] == 0 and map[row][column+1] == 0 and map[row-1][column] == 0:
movements.append((row-1,column+1))
if row < rows-1 and column > 0:
if map[row+1][column-1] == 0 and map[row][column-1] == 0 and map[row+1][column] == 0:
movements.append((row+1,column-1))
if row < rows-1 and column < columns-1:
if map[row+1][column+1] == 0 and map[row][column+1] == 0 and map[row+1][column] == 0:
movements.append((row+1,column+1))
dictionary[(row,column)] = movements
def pathfind(startx,starty,endx,endy):
global rows,columns,map,dictionary,path,success
if mapstat and dictionary != {}:
if map[startx][starty] == 0 and map[endx][endy] == 0 and len(dictionary[(startx,starty)]) != 0 and len(dictionary[(endx,endy)]) != 0:
paths = [[(startx,starty)]]
complete = []
while len(paths) > 0 and complete == []:
currpath = paths[0]
paths.remove(currpath)
if currpath[-1] == (endx,endy):
complete = currpath
else:
for way in dictionary[currpath[-1]]:
if not(way in currpath):
paths.append(currpath+[way])
if complete != []:
path = complete
success = true
else:
success = false
Steps:
Map is set to your grid, pretty easy.
Run checkmap()
Run builddic()
Run pathfind(startx,starty,endx,endy)
The results are saved as global path. To retrieve them, run this command:
Code:
global path
somevar = path
where somevar is the variable where the results should be saved.
'Apple Macintosh' - An anagram of 'Complaints Heap'
M.A.C.I.N.T.O.S.H. - Machine Always Crashes, If Not, The Operating System Hangs.
You're *such* a mac person.
Last edited by zonedabone; 06-16-2010 at 09:14 PM.
|
|
|
|
|
Guest
|
06-16-2010, 08:06 PM
That's a pretty good start to it. You could also try and merge the global arrays into one single multidimensional array as well as trying to implement a sorting routine such as binary heaps to make it even faster .
|
|
|
|
|
Senior Member
Status: Offline
Posts: 577
Join Date: Nov 2008
Location: In the interwebs
|
06-16-2010, 09:14 PM
It already is a multidimensional array.
Also, I just made it better so it quits after it finds the first path, which is always the best one in the new code.
Code:
map = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
mapstat = false
rows = 0
columns = 0
dictionary = {}
path = []
success = false
def checkmap():
global mapstat,rows,columns,map
if len(map) == 0:
mapstat = false
return
rows = []
for row in map:
rows.append(len(row))
if rows[0] == 0:
mapstat = false
return
rowconform = rows[0]
for lens in rows:
if lens != rowconform:
mapstat = false
return
mapstat = true
rows = len(map)
columns = rowconform
def builddic():
global rows,columns,mapstat,dictionary,map
if mapstat == true:
for row in range(rows):
for column in range(columns):
if map[row][column] == 0:
movements = []
if row > 0:
if map[row-1][column] == 0:
movements.append((row-1,column))
if row < rows-1:
if map[row+1][column] == 0:
movements.append((row+1,column))
if column > 0:
if map[row][column-1] == 0:
movements.append((row,column-1))
if column < columns-1:
if map[row][column+1] == 0:
movements.append((row,column+1))
if row > 0 and column > 0:
if map[row-1][column-1] == 0 and map[row][column-1] == 0 and map[row-1][column] == 0:
movements.append((row-1,column-1))
if row > 0 and column < columns-1:
if map[row-1][column+1] == 0 and map[row][column+1] == 0 and map[row-1][column] == 0:
movements.append((row-1,column+1))
if row < rows-1 and column > 0:
if map[row+1][column-1] == 0 and map[row][column-1] == 0 and map[row+1][column] == 0:
movements.append((row+1,column-1))
if row < rows-1 and column < columns-1:
if map[row+1][column+1] == 0 and map[row][column+1] == 0 and map[row+1][column] == 0:
movements.append((row+1,column+1))
dictionary[(row,column)] = movements
def pathfind(startx,starty,endx,endy):
global rows,columns,map,dictionary,path,success
if mapstat and dictionary != {}:
if map[startx][starty] == 0 and map[endx][endy] == 0 and len(dictionary[(startx,starty)]) != 0 and len(dictionary[(endx,endy)]) != 0:
paths = [[(startx,starty)]]
complete = []
while len(paths) > 0 and complete == []:
currpath = paths[0]
paths.remove(currpath)
if currpath[-1] == (endx,endy):
complete = currpath
else:
for way in dictionary[currpath[-1]]:
if not(way in currpath):
paths.append(currpath+[way])
if complete != []:
path = complete
success = true
else:
success = false
'Apple Macintosh' - An anagram of 'Complaints Heap'
M.A.C.I.N.T.O.S.H. - Machine Always Crashes, If Not, The Operating System Hangs.
You're *such* a mac person.
|
|
|
|
|
Senior Member
Status: Offline
Posts: 577
Join Date: Nov 2008
Location: In the interwebs
|
06-17-2010, 11:02 AM
I've now made a demo of it. It's in the share worlds section.
'Apple Macintosh' - An anagram of 'Complaints Heap'
M.A.C.I.N.T.O.S.H. - Machine Always Crashes, If Not, The Operating System Hangs.
You're *such* a mac person.
|
|
|
|
|
Super Moderator
Status: Offline
Posts: 3,508
Join Date: Dec 2008
Location: Somewhere in the Continental U.S.
|
06-17-2010, 12:42 PM
Nice, very very nice.
|
|
|
Thread Tools |
|
Display Modes |
Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
Copyright ©2024, Carnegie Mellon University
Alice 2.x © 1999-2012, Alice 3.x © 2008-2012, Carnegie Mellon University. All rights reserved.
|
|