DIR Return Create A Forum - Home
---------------------------------------------------------
Pirates IRC
HTML https://piratesirc.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: General Discussion
*****************************************************
#Post#: 140--------------------------------------------------
Help Wanted!
By: mruno Date: August 20, 2022, 8:13 pm
---------------------------------------------------------
Need help with pathfinding. The current function does not
account for land masses, so ships travel in a straight or
diagonal line
The current code is at:
HTML https://pastebin.com/0HpARBL4
The list of cells which are land, sea, or both is at:
HTML https://pastebin.com/Var7ucfG
#Post#: 154--------------------------------------------------
Re: Help Wanted!
By: dclaw Date: December 27, 2023, 5:53 pm
---------------------------------------------------------
No idea what I'm doing. But maybe this would work.
HTML https://pbr.piss.bee
r/?829563e4962452c9#48PXgipRxH18MKngWbccsMKmSjxQEJP73KpwxbyRx3rt
EDIT: It apparently doesn't like my pastebin domain. the
asterisk is p i s s
#Post#: 157--------------------------------------------------
Re: Help Wanted!
By: oi Date: August 20, 2024, 12:26 am
---------------------------------------------------------
I don't have it ported to mirc, not familiar with the language,
this is in python. There's no port-name lookup, but otherwise it
should be usable at a starting point.
[code]
"""
Pirate Python Path Plotter
by oi o' the phreak, August 2024
"""
# stdlib
import sys
from queue import PriorityQueue
DEBUG = False
def pathplotter(startPos, destPos):
""" Get the shortest path, as a string, from start to dest,
or an error msg if the inputs are invalid """
cellsFilepath = "cells.txt" # from
HTML https://pastebin.com/L94JBf0E
accessibleFeatures = ["sea","both"]
board = Board(cellsFilepath, accessibleFeatures)
if(board.validateCell(startPos) == False or
board.validateCell(destPos) == False):
return("Invalid coordinates")
if(board.getCell(destPos).accessible == False):
return("Inaccessible destination")
path = getPath(board, startPos, destPos)
return(serializePath(path))
# ------------------------ Pathfinding
-------------------------------------
def serializePath(path):
""" Get a string version of the path for output printing """
pathstring = ""
for c in path:
pathstring += f"{c.position},"
# chomp the last comma
pathstring = pathstring[:-1]
return pathstring
def getPath(board, startPos, destPos):
""" Search the board for distance-cost to each other cell,
then get lowest cost path to the destination """
cameFrom = uniformCostSearch(board, startPos, destPos)
path = followPath(board, cameFrom, startPos, destPos)
return path
def uniformCostSearch(board, startPos, destPos):
""" Determine distance cost to every other cell on the board
Cribbed from
HTML https://www.redblobgames.com/pathfinding/a-star/
"""
startCell = board.getCell(startPos)
frontier = PriorityQueue()
frontier.put((0, startCell))
cameFrom = dict() # path A->B is stored as came_from[B] == A
costSoFar = dict()
cameFrom[startCell] = None
costSoFar[startCell] = 0
# Do the search
while not frontier.empty():
currentCell = frontier.get()
if(currentCell[1].cellPos == destPos):
break;
neighbours = currentCell[1].getNeighbours(board)
for neighbour in neighbours:
if(neighbour.accessible):
neighbourCost = 1
else:
neighbourCost = 999
newCost = costSoFar[currentCell[1]] + neighbourCost
if neighbour.cellPos not in cameFrom or newCost <
costSoFar[neighbour]:
costSoFar[neighbour] = newCost
priority = newCost
frontier.put((priority, neighbour))
cameFrom[neighbour.cellPos] =
currentCell[1].cellPos
return cameFrom
def followPath(board, cameFrom, startPos, destPos):
""" Calculate the path from the destination to the start """
startCell = board.getCell(startPos)
currentCell = board.getCell(destPos)
path = []
while currentCell != startCell:
path.append(currentCell)
newPos =
cameFrom[board.getCell(currentCell.cellPos).cellPos]
currentCell = board.getCell(newPos)
path.append(startCell) # optional
path.reverse() # optional
return path
# --------------------------- Classes
---------------------------------------
class Board(object):
rows = 16
cols = 19
def __init__(self, cellsFilepath, accessibleFeatures):
self.cells = self.defineCells(cellsFilepath,
accessibleFeatures)
def validateCell(self, cellPos):
""" Is the cell code (eg A1) a valid coordinate for the
board? """
try:
self.getCell(cellPos)
return True
except:
return False
def getCell(self, cellPos):
""" Get the cell object corresponding to a coordinate
string (eg A1) """
row = int(cellPos[1:]) - 1 # zero-indexed
col = ord(cellPos[0].lower()) - 96 - 1 # the magic
numbers are used to convert ascii letters to zero-indexed
numbers
return self.cells[row][col]
def defineCells(self, cellsFilepath, accessibleFeatures):
""" Convert the input cell definition file into a list
of dicts """
lines = []
with open(cellsFilepath, "r") as fp:
for l in fp:
lines.append(l.strip())
# Get an array of dimensions arr[cols][rows].
cells = []
for i in range(0, self.rows):
innerList = []
for j in range(0, self.cols):
innerList.append(None)
cells.append(innerList)
# Fill the array with cells generated from lines in the
textfile
for line in lines:
cell = Cell(line, accessibleFeatures)
cells[cell.row][cell.col] = cell
if(DEBUG): print(cell)
return cells
class Cell(object):
def __init__(self, line, accessibleFeatures):
# Parse the text from the input cells.txt file
self.priority = 0
self.cellPos, self.featureType = line.split("=")
self.cellPos = self.cellPos.upper()
self.row = int(self.cellPos[1:]) - 1 # zero-indexed
self.col = ord(self.cellPos[0].lower()) - 96 - 1
self.position = self.cellPos.upper()
self.rowName = self.cellPos[1:]
self.colName = self.cellPos[0].upper()
self.accessible = self.featureType in accessibleFeatures
def __lt__(self, value):
return True
def __str__(self):
""" used for debugging """
return f"{self.cellPos}\tRow: {self.row}\tCol:
{self.col}\tType: {self.featureType}\tAccess: {self.accessible}"
def getNeighbours(self, board):
""" Get coordinates for valid neighbouring cells. 2 in a
corner, 3 on an edge, 4 elsewhere """
if(self.row < 0 or self.col < 0):
return None
elif(self.row >= board.rows or self.col >= board.cols):
return None
neighbours = []
#North, South, East, West
if(self.row + 1 < board.rows):
neighbours.append(board.cells[self.row +
1][self.col])
if(self.row > 0):
neighbours.append(board.cells[self.row -
1][self.col])
if(self.col + 1 < board.cols):
neighbours.append(board.cells[self.row][self.col +
1])
if(self.col > 0):
neighbours.append(board.cells[self.row][self.col -
1])
return neighbours
[/code]
*****************************************************