I have a project to do and I'm pretty lost on it. The purpose of the project is to make a game like quoridor, but for this part you only need to have your program ready walls from a file (Walls are given in the format of: (startx, starty)(endx, endy) but are in the file as something like 5 7 7 7, separated by lines. I don't really think that I can get into everything but I'll try to summarize my current problem.

Right now I'm doing this by creating a board, and while creating the graph of the board I'm adding in the neighbors to each node. Afterwards, when I read the walls from the file I will remove the appropriate neighbor adjacencies. Long story short, if there is say a vertical wall in between 2 nodes, I want to remove the node on the right side of the wall as a neighbor to the node on the left side of it. I originally stored the neighbors as tuples in a list so I thought I could remove the index of the tuple from the list. I eventually realized however that if the node was on a wall or corner it would have less neighbors so my code would only work for nodes in the middle of the graph.

It's really hard to explain everything about this project and I know my description is probably confusing, but I'll add my code to the bottom and try to answer any questions. I just need some suggestions as to how to remove neighbors from any square regardless of whether or not it started on a wall and has less neighbors in the list.

ALSO: After building the board I'm going to have to do a shortest path search, probably by using a breadth first search through the graph and then return the shortest path. So if anyone has any insight on that, that'd be great.

CODE (Lines 36-74 are where I'm having the problem):

from interface import *
import engine

"""
The player module is called by the engine to conduct game play.  You should
not modify the signatures for the init(), shortest_path(), move() 
and last_move() functions.  You are free to implement any other routines or modules.

Author: YOUR NAME HERE
"""

# public routines

def init(gameFile, playerId, numPlayers, playerHomes, wallsRemaining):
    """
    For all parts the engine calls this method so the player can initialize their data.
        gameFile - a string which is the file containing the initial board state.
        playerId - the numeric Id of the player (0-4).
        numPlayers - the number of players (2 or 4).
        playerHomes - a list of coordinates for each players starting cell (PO-P4).
        wallsRemaining - the number of walls remaining (same for all players at start).
    """
    
    # log any message string to standard output and the current log file
    engine.log_msg("player.init called for player " + str(playerId) + " File=" + gameFile +
                   ', playerId=' + str(playerId) + ', numPlayers=' + str(numPlayers) + ', playerHomes=' +
                   str(playerHomes) + ', wallsRemaining=' + str(wallsRemaining))
    
    playerData = None
    class playerData(object):
        __slots__ = (board)
        
    class node(object):
        __slots__ = (row, column, neighbors, previous)
        
    def createBoard():
        board = []
            for i in range(9):
                row = []
                for j in range(9):
                    row.append(node(i,j,[],[]))
                    if i != 0:
                        row[j].neighbors.append((i-1,j))
                    if i != 8:
                        row[j].neighbors.append((i+1,j))
                    if j != 0:
                        row[j].neighbors.append((i,j-1))
                    if j != 8:
                        row[j].neighbors.append((i,j+1))
                 board.append(row)
        return board
        
    def addWalls(filename,board):
        walls = []
        for line in open (filename):
            walls.append([line])
        for element in range(0,len(walls)-1):
            if walls[element][0] != walls[element][2]:
                # Wall is vertical
                # Following line gets the coordinate of the top left box 
                # of the 4 boxes separated in the middle by a vertical line
                node = board[walls[element][0]][walls[element][1]-1]
                node.neighbors.remove(3)
                """ This removes the fourth element because the neighbors
                are created in the order of top, bottom, left, right so
                by removing the 4th element of the list you remove the 
                right neighbor, this works since we're on the left side 
                of the vertical wall"""
                node = board[walls[element][0]+1][walls[element][1]-1]
                node.neighbors.remove(3)
                node = board[walls[element][0]][walls[element][1]]
                node.neighbors.remove(2)
                node = board[walls[element][0]+1][walls[element][1]]
                node.neighbors.remove(2)
                
                
            
        
        
                
    # initialize your data structure here, and then return it.  It will be
    # passed back to you as 'playerData' in the shortest_path function.

    return playerData

def shortest_path(playerData, source, dest):
    """Returns a list of coordinates representing the shortest path on the
    board between the start and finish coordinates.
        playerData - The player's data
        source - the start coordinate
        dest - the end coordinate
    """
    
    engine.log_msg("player.shortest_path called.  Source: " + str(source) + 
                   ", Dest: " + str(dest))
    count = 0
    childern = []
    open = []
    path = []
    open.append(source)
    closed = []
    while open != []:
        x = open[0]
        open.remove(0)
        if x == dest:
            return path
        else:
            for name in source.neighbor:
                childern.append(name)
            closed.append(x)
            for element in childern:
                count =+ 1
                if element in closed or in open:
                    childern.remove(count-1)
                else:
                    open.append(element)
    # Implement your shortest path algorithm here.  If no path is found
    # return an empty list.
    
    return path

Update, I think that my wall code works now, which removes the neighbors based on where the walls are. I feel like this is too much work to be the right way to do it, but logically I think it should work for every wall.

def addWalls(filename,board):
        walls = []
        for line in open (filename):
            walls.append([line])
        for element in range(0,len(walls)-1):
            if walls[element][0] != walls[element][2]:
                # Wall is vertical
                # Following line gets the coordinate of the top left box 
                # of the 4 boxes separated in the middle by a vertical line
                node = board[walls[element][0]][walls[element][1]-1]
                compare = board[node.coordinates[0]][node.coordinates[1]+1]
                for element in node.neighbors:
                    if node.neighbors[element] == compare.coordinates:
                        node.neighbors.remove(element)
                for element in compare.neighbors:
                    if compare.neighbors[element] == node.coordinates:
                        compare.neighbors.remove(element)
                """ This removes the fourth element because the neighbors
                are created in the order of top, bottom, left, right so
                by removing the 4th element of the list you remove the 
                right neighbor, this works since we're on the left side 
                of the vertical wall
                
                EDIT: This now sets up a comparison between the 2 side 
                by side neighbors and removes both from each others 
                neighbor list."""
                node = board[walls[element][0]+1][walls[element][1]-1]
                compare = board[node.coordinates[0]][node.coordinates[1]+1]
                for element in node.neighbors:
                    if node.neighbors[element] == compare.coordinates:
                        node.neighbors.remove(element)
                for element in compare.neighbors:
                    if compare.neighbors[element] == node.coordinates:
                        compare.neighbors.remove(element)
            else:
                # Walls Horizontal
                node = board[walls[element][0]-1][walls[element][1]]
                compare = board[node.coordinates[0]+1][node.coordinates[1]]
                for element in node.neighbors:
                    if node.neighbors[element] == compare.coordinates:
                        node.neighbors.remove(element)
                for element in compare.neighbors:
                    if compare.neighbors[element] == node.coordinates:
                        compare.neighbors.remove(element)
                node = board[walls[element][0]-1][walls[element][1]+1]
                compare = board[node.coordinates[0]+1][node.coordinates[1]]
                for element in node.neighbors:
                    if node.neighbors[element] == compare.coordinates:
                        node.neighbors.remove(element)
                for element in compare.neighbors:
                    if compare.neighbors[element] == node.coordinates:
                        compare.neighbors.remove(element)

What I really need help with now is with the shortest path function.

Currently it is this:

count = 0
    childern = []
    open = []
    path = []
    open.append(source)
    closed = []
    while open != []:
        x = open[0]
        open.remove(0)
        if x == dest:
            current = dest
            while current.previous != []:
                path.append(current.previous)
                current = current.previous 
            return path
        else:
            for name in source.neighbor:
                childern.append(name)
            closed.append(x)
            for element in childern:
                count =+ 1
                if element in closed or open:
                    childern.remove(count-1)
                else:
                    element.previous.append(x)
                    open.append(element)

I know that this doesn't work, but I'm unsure how to build a path of tuples to return at the end. Also in the first few lines I get an error saying that there is no element x to remove from the "open.remove(0)" line. So if anyone knows how to fix that, that'd be wonderful

I would not use open as variable name, as it hides file open command, maybe change to open_ones or something.
You can replace 7 to 9 lines with

while open_ones:
   x = open_ones.pop(0)

Edited 5 Years Ago by pyTony: n/a

if destination in visited:
        tmp = destination
        while tmp != source:
            push((tmp.row,tmp.column), stack)
            tmp = tmp.previous
        push((source.row,source.column), stack)

Is how you push the coordinates to the stack as a tuple.
"(source.row,source.column)" is the tuple.

Also, what is node.coordinates? Your node class says nothing about coordinates...

Well I noticed your not using a stack class but same thing applies for the tuple. You just want it in the form of "(node.row,node.column)"

Well, I never really got this to work completely but I ran out of time on the project.

To answer your questions:
node.coordinates was what I switched the x and y variables in the class to. Instead of storing 2 different values, I stored them as a tuple of coordinates.

Also, In class we were encouraged to use a queue instead of a stack, because if you check each node and add its neighbors to the back of the queue if the node is not the destination and keep doing that then you are guaranteed to get the shortest path in the end.

This article has been dead for over six months. Start a new discussion instead.