Aktualizacja: przepisałem back-end aplikacji na TypeScript. Front-end będzie prawdopodobnie prostszy, więc na razie odpuszczam; konfigurację podawaną docelowo z linii komend tymczasowo zmockowałem.
Co do samego generowania linii: ukułem algorytm (wspomniany w poście wyżej), który działa mniej-więcej w ten sposób: chodzi po "komórkach" i sprawdza, czy dana komórka jest "wolna"; jeśli tak, to dodaje ją do ścieżki – a jeśli nie, to nie. Wynikowe ścieżki generuję dwa razy: raz – dla diagramu "zwykłego" (nazwanego diagram
), a dwa – dla diagramu "grafowego" (nazwanego graphDiagram
), czyli diagramu tworzonego na podstawie grafu.
Aplikacja w sumie powinna działać – ale nie działa. Problem jest w algorytmie – a w każdym razie największy problem, jak go oceniam; z innymi wydaje się, że sobie poradziłem / poradzę. Zamieszczam kod algorytmu poniżej – może ktoś będzie wiedział.
Traversal
To jest klasa z metodą traverse
, czyli implementacją algorytmu.
import Deque from "../../utils/deque"; // moja implementacja kolejki dwukierunkowej – nie czepiajcie się…
import Move from "../space/move";
import MyPosition from "./my-position";
import Step from "./step";
/**
* Represents a traversal on a set of positions.
*/
export default class Traversal {
private path: Deque<Step>;
private forbiddenMoves: { from: MyPosition, to: MyPosition }[];
private isTargetPosition!: (myPosition: MyPosition) => boolean;
private isPositionForbidden!: (myPosition: MyPosition) => boolean;
constructor() {
this.path = new Deque<Step>();
this.forbiddenMoves = [];
}
private getLastStep(): Step {
return this.path.getLastElement();
}
private getPreviousPosition(): MyPosition | undefined {
return this.getLastStep().previousPosition;
}
private getCurrentPosition(): MyPosition {
return this.getLastStep().currentPosition;
}
private stepBack(): void {
this.path.popBack();
}
private isSteppingBackMove(move: Move | undefined): boolean {
const lastStep: Step = this.getLastStep();
return lastStep.moveThatLed === undefined
? false
: lastStep.moveThatLed.isEqualTo(move);
}
private move(move: Move): void {
const currentPosition: MyPosition = this.getCurrentPosition();
this.path.pushBack(
new Step(
currentPosition,
move,
move.forward.displaceFrom(currentPosition)
)
);
}
private movedBeforeBetween(myPosition1: MyPosition, myPosition2: MyPosition): boolean {
return this.path.find((step) =>
step.previousPosition === undefined
? false
: step.previousPosition.isEqualTo(myPosition1)
&& step.currentPosition.isEqualTo(myPosition2)
) !== undefined;
}
private evaluateNextPosition(move: Move): MyPosition {
return move.forward.displaceFrom(this.getCurrentPosition());
}
private isMoveForbiddenBetween(
myPosition1: MyPosition, myPosition2: MyPosition
): boolean {
return this.forbiddenMoves.find((fm) =>
fm.from.isEqualTo(myPosition1) && fm.to.isEqualTo(myPosition2)
) !== undefined;
}
private forbidMoveBetween(myPosition1: MyPosition, myPosition2: MyPosition): void {
console.debug(`\tForbidding move from ${myPosition1} to ${myPosition2} ...`);
this.forbiddenMoves.push({ from: myPosition1, to: myPosition2 });
}
private findPossibleMoveFrom(myPosition: MyPosition): Move | undefined {
return MyPosition.moves.find((m) => {
const nextPosition: MyPosition = this.evaluateNextPosition(m);
return !this.isSteppingBackMove(m)
&& !this.isMoveForbiddenBetween(myPosition, nextPosition)
&& !this.movedBeforeBetween(
this.getCurrentPosition(), nextPosition
)
&& !this.isPositionForbidden(nextPosition);
});
}
setWhatPositionsTarget(
isTargetPosition: (myPosition: MyPosition) => boolean
): Traversal {
this.isTargetPosition = isTargetPosition;
return this;
}
setWhatPositionsForbidden(
isForbiddenPosition: (myPosition: MyPosition) => boolean
): Traversal {
this.isPositionForbidden = isForbiddenPosition;
return this;
}
setStartPosition(startPosition: MyPosition): Traversal {
const stepZero: Step = new Step(undefined, undefined, startPosition);
this.path.pushBack(stepZero);
return this;
}
traverse(): Deque<Step> {
let i = 0;
while (true) {
const currentPosition: MyPosition = this.getCurrentPosition();
console.debug(`Now on ${currentPosition} (Iteration no. ${++i})`);
if (this.isTargetPosition(currentPosition)) {
console.debug(`Target reached at ${currentPosition}`);
return this.path;
}
const possibleMove: Move | undefined
= this.findPossibleMoveFrom(currentPosition);
if (possibleMove === undefined) {
const previousPosition: MyPosition | undefined
= this.getPreviousPosition();
if (previousPosition === undefined) {
console.debug(`Cannot found target`);
return this.path;
}
this.forbidMoveBetween(previousPosition, currentPosition);
this.stepBack();
} else {
this.move(possibleMove);
}
}
}
}
W taki zaś sposób metoda traverse
jest wywoływana:
// Klasa Board
findPath(
startPosition: MyPosition,
isTargetPosition: (myPosition: MyPosition) => boolean,
isPositionForbidden: (myPosition: MyPosition) => boolean
): Deque<Step> {
const traversal: Traversal
= new Traversal()
.setStartPosition(startPosition)
.setWhatPositionsTarget(isTargetPosition)
.setWhatPositionsForbidden(isPositionForbidden);
const path: Deque<Step> = traversal.traverse();
return path;
}
Prawdopodobnie do zrozumienia kodu będą potrzebne jeszcze następujące trzy klasy:
Move
import Displacement from "../space/displacement";
import IEqualComparable from "../../utils/interfaces/i-equal-comparable";
/**
* Represents a subset of all possible displacements from a point to another
* one.
*/
export default class Move implements IEqualComparable<Move> {
readonly name: string;
readonly forward: Displacement;
readonly backward: Displacement;
constructor(name: string, forward: Displacement, backward: Displacement) {
this.name = name;
this.forward = forward;
this.backward = backward;
}
isEqualTo(move: Move | undefined): boolean {
return move === undefined ? false : this.name === move.name;
}
}
MyPosition
W Node jest już interfejs o takiej nazwie, dlatego też dodałem przedrostek my
.
import Coordinate from "../space/coordinate";
import Point from "../space/point";
import Displacement from "../space/displacement";
import Move from "../space/move";
/**
* Represents a point in a space, which point "knows" how to move to another
* one.
*/
export default class MyPosition extends Point {
private static readonly displacements:
{
topward: Displacement,
rightward: Displacement,
bottomward: Displacement,
leftward: Displacement,
}
= {
topward:
new Displacement(
(myPosition: MyPosition) =>
new MyPosition(
myPosition.x, myPosition.y.getDecremented()
)
),
rightward:
new Displacement(
(myPosition: MyPosition) =>
new MyPosition(
myPosition.x.getIncremented(), myPosition.y
)
),
bottomward:
new Displacement(
(myPosition: MyPosition) =>
new MyPosition(
myPosition.x, myPosition.y.getIncremented()
)
),
leftward:
new Displacement(
(myPosition: MyPosition) =>
new MyPosition(
myPosition.x.getDecremented(), myPosition.y
)
)
};
static readonly moves: Move[]
= [
new Move(
"topward",
MyPosition.displacements.topward,
MyPosition.displacements.bottomward
),
new Move(
"rightward",
MyPosition.displacements.rightward,
MyPosition.displacements.leftward
),
new Move(
"bottomward",
MyPosition.displacements.bottomward,
MyPosition.displacements.topward
),
new Move(
"leftward",
MyPosition.displacements.leftward,
MyPosition.displacements.rightward
)
];
protected constructor(x: Coordinate, y: Coordinate) {
super(x, y);
}
}
Step
import Move from "../space/move";
import MyPosition from "./my-position";
import IEqualComparable from "../../utils/interfaces/i-equal-comparable";
/**
* Represents a step in a traversal on a set of positions.
*/
export default class Step implements IEqualComparable<Step> {
previousPosition: MyPosition | undefined;
moveThatLed: Move | undefined;
currentPosition: MyPosition;
constructor(
previousPosition: MyPosition | undefined,
moveThatLed: Move | undefined,
currentPosition: MyPosition
) {
this.previousPosition = previousPosition;
this.moveThatLed = moveThatLed;
this.currentPosition = currentPosition;
}
isEqualTo(step: Step | undefined): boolean {
const previousPositionsEqual: boolean
= (this.previousPosition === undefined
&& step!.previousPosition === undefined)
|| this.previousPosition!.isEqualTo(step!.previousPosition);
const movesThatLedEqual: boolean
= (this.moveThatLed === undefined
&& step!.previousPosition === undefined)
|| this.moveThatLed!.isEqualTo(step!.moveThatLed);
const currentPositionsEqual: boolean
= this.currentPosition.isEqualTo(step!.currentPosition);
return step === undefined
? false
: previousPositionsEqual
&& movesThatLedEqual
&& currentPositionsEqual;
}
}
(Tak, wydaje się, że nasze forum nie obsługuje kolorowania składni TypeScriptu).
Wiem, że do oceny działania algorytmu potrzeba by całego programu; ale raz, że nie chcę kodu na GitHubie umieszczać – bo nie działa – a dwa, że w treści posta umieściwszy byłby on całkiem nieczytelny (plików *.ts
– licząc back-end i pliki utils – jest 35).
Jeśli więc ktoś chciałby się nad tym pochylić…
PS. Kod może wydawać się "ściśnięty" wizualnie na szerokość, bo w projekcie celuję w 80-kolumnowe linie. Tak po prostu przyjąłem – nie wiem, czy to źle, czy dobrze.
PS2. Jakby ktoś miał jakieś uwagi do kodu – zbyt rozwlekły, zbyt lakoniczny, za wiele metod, za mało metod, zbyt generyczny, za mało generyczny… to pisać! Przyda mi się każda uwaga.