Alice Community  

Go Back   Alice Community > Alice 2 > Works-In-Progress

Reply
 
Thread Tools Display Modes
Jython Pathfinding!
Old
zonedabone
Senior Member
 
zonedabone's Avatar
 
Status: Offline
Posts: 578
Join Date: Nov 2008
Location: In the interwebs
Default 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.
   
Reply With Quote
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Default 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 .
   
Reply With Quote
Old
zonedabone
Senior Member
 
zonedabone's Avatar
 
Status: Offline
Posts: 578
Join Date: Nov 2008
Location: In the interwebs
Default 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.
   
Reply With Quote
Old
zonedabone
Senior Member
 
zonedabone's Avatar
 
Status: Offline
Posts: 578
Join Date: Nov 2008
Location: In the interwebs
Default 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.
   
Reply With Quote
Old
x2495iiii
Super Moderator
 
x2495iiii's Avatar
 
Status: Offline
Posts: 3,508
Join Date: Dec 2008
Location: Somewhere in the Continental U.S.
Default 06-17-2010, 12:42 PM

Nice, very very nice.


(')>
   
Reply With Quote
Reply

Tags
zonedabone

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Copyright ©2019, Carnegie Mellon University
Alice 2.x 1999-2012, Alice 3.x 2008-2012, Carnegie Mellon University. All rights reserved.