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
