Cocoban Game Prolog Debugging
Budget: €8 – €30 EUR
We need to fix this cocoban game such as it solves for also cases where we have 2 objects near each other. Need this fixed by 20.00 this day if someone fixes it i can offer even higher price. Maybe some explenation what was wrong would be nice.
% Import necessary libraries
:- use_module(library(readutil)).
:- dynamic wall/2, crate/2, storage/2, sokoban/2.
% --- Map Loading ---
load_map(File) :-
retractall(wall(_, _)),
retractall(crate(_, _)),
retractall(storage(_, _)),
retractall(sokoban(_, _)),
read_file_to_string(File, MapString, []),
split_string(MapString, "\n", "", Lines),
exclude(=(""), Lines, NonEmptyLines),
parse_lines(NonEmptyLines, 0).
parse_lines([], _).
parse_lines([Line | Rest], Row) :-
string_chars(Line, Chars),
assert_line(Chars, Row, 0),
NewRow is Row + 1,
parse_lines(Rest, NewRow).
assert_line([], _, _).
assert_line([Char | Rest], Row, Col) :-
( Char = '#' -> assertz(wall(Row, Col))
; Char = 'C' -> assertz(crate(Row, Col))
; Char = 'X' -> assertz(storage(Row, Col))
; Char = 'S' -> assertz(sokoban(Row, Col))
; Char = 'c' -> assertz(crate(Row, Col)), assertz(storage(Row, Col))
; Char = 's' -> assertz(sokoban(Row, Col)), assertz(storage(Row, Col))
; true
),
NextCol is Col + 1,
assert_line(Rest, Row, NextCol).
% --- Helper Predicates ---
valid_position(X, Y) :-
\+ wall(X, Y).
goal_state(Crates) :-
findall((X, Y), storage(X, Y), StoragePositions),
sort(Crates, SortedCrates),
sort(StoragePositions, SortedCrates),
sokoban_can_exit(Crates).
sokoban_can_exit(Crates) :-
sokoban(SX, SY),
findall(Direction, valid_action((SX, SY), Crates, _, _, move(Direction)), ValidMoves),
ValidMoves \= [].
sokoban_trapped(Sokoban, Crates) :-
sokoban(SX, SY),
findall(Direction, valid_action((SX, SY), Crates, _, _, move(Direction)), Moves),
Moves == []. % Sokoban has no valid moves
state(Sokoban, Crates) :-
sokoban(SX, SY), Sokoban = (SX, SY),
findall((CX, CY), crate(CX, CY), Crates).
move(Direction, (SX, SY), (NX, NY)) :-
direction_delta(Direction, DX, DY),
NX is SX + DX,
NY is SY + DY,
valid_position(NX, NY),
\+ crate(NX, NY).
push(Direction, (SX, SY), Crates, (NX, NY), NewCrates) :-
direction_delta(Direction, DX, DY),
NX is SX + DX,
NY is SY + DY,
TX is NX + DX,
TY is NY + DY,
member((NX, NY), Crates),
valid_position(TX, TY),
\+ member((TX, TY), Crates),
select((NX, NY), Crates, CratesTmp),
append([(TX, TY)], CratesTmp, NewCrates).
direction_delta(up, -1, 0).
direction_delta(down, 1, 0).
direction_delta(left, 0, -1).
direction_delta(right, 0, 1).
% --- Deadlock Detection ---
deadlock(Crates) :-
member((X, Y), Crates),
\+ storage(X, Y),
( (wall(X-1, Y), wall(X, Y-1))
; (wall(X-1, Y), wall(X, Y+1))
; (wall(X+1, Y), wall(X, Y-1))
; (wall(X+1, Y), wall(X, Y+1))
).
count_deadlock_risks(Crates, Penalty) :-
findall(1, (member((X, Y), Crates), is_deadlock_position((X, Y))), DeadlockPositions),
length(DeadlockPositions, Penalty).
is_deadlock_position((X, Y)) :-
\+ storage(X, Y),
((wall(X-1, Y), wall(X, Y-1));
(wall(X-1, Y), wall(X, Y+1));
(wall(X+1, Y), wall(X, Y-1));
(wall(X+1, Y), wall(X, Y+1))).
% --- BFS Solver ---
solve(File) :-
load_map(File),
state(Sokoban, Crates),
bfs([(Sokoban, Crates, [])], [], [], Solution),
reverse(Solution, OrderedSolution),
write("Solution: "), nl, write(OrderedSolution), nl,
animate_solution(OrderedSolution).
bfs([], _, _, _) :-
write("No solution found."), nl, fail.
bfs([(Sokoban, Crates, Path) | _], _, _, Path) :-
write("Current Sokoban: "), write(Sokoban), nl,
write("Current Crates: "), write(Crates), nl,
write("Current Path: "), write(Path), nl,
goal_state(Crates),
\+ deadlock(Crates),
!.
bfs([(Sokoban, Crates, Path) | Rest], Visited, Explored, Solution) :-
findall(
(NextSokoban, NextCrates, [Action | Path]),
(valid_action(Sokoban, Crates, NextSokoban, NextCrates, Action),
\+ member((NextSokoban, NextCrates), Visited),
\+ member((NextSokoban, NextCrates), Explored),
\+ deadlock(NextCrates),
sokoban_can_exit(NextCrates)),
NextStates
),
prioritize_states(NextStates, SortedStates),
append(Rest, SortedStates, Queue),
bfs(Queue, [(Sokoban, Crates) | Visited], [(Sokoban, Crates) | Explored], Solution).
valid_action(Sokoban, Crates, NextSokoban, Crates, move(Direction)) :-
move(Direction, Sokoban, NextSokoban),
\+ member(NextSokoban, Crates). % Sokoban cannot move into a crate's position
valid_action(Sokoban, Crates, NextSokoban, NextCrates, push(Direction)) :-
push(Direction, Sokoban, Crates, NextSokoban, NextCrates).
% --- Prioritize States ---
prioritize_states(States, SortedStates) :-
maplist(score_state, States, ScoredStates),
sort(2, @=<, ScoredStates, SortedScoredStates),
maplist(remove_score, SortedScoredStates, SortedStates).
score_state((Sokoban, Crates, Path), ((Sokoban, Crates, Path), Score)) :-
findall(Distance, (member(Crate, Crates), crate_to_storage_distance(Crate, Distance)), CrateDistances),
sum_list(CrateDistances, TotalCrateToStorageDistance),
findall(Distance, (member(Crate, Crates), manhattan_distance(Sokoban, Crate, Distance)), SokobanDistances),
min_list(SokobanDistances, SokobanToClosestCrateDistance),
count_deadlock_risks(Crates, DeadlockPenalty),
Score is TotalCrateToStorageDistance * 10 + SokobanToClosestCrateDistance + DeadlockPenalty.
remove_score(((Sokoban, Crates, Path), _), (Sokoban, Crates, Path)).
% --- Distance Calculation Helpers ---
crate_to_storage_distance((CX, CY), Distance) :-
findall(D, (storage(SX, SY), manhattan_distance((CX, CY), (SX, SY), D)), Distances),
min_list(Distances, Distance).
manhattan_distance((X1, Y1), (X2, Y2), Distance) :-
Distance is abs(X1 - X2) + abs(Y1 - Y2).
% --- Visualization ---
animate_solution([]).
animate_solution([Action | Rest]) :-
write('Action: '), write(Action), nl,
perform_action(Action),
display_map,
sleep(0.5),
animate_solution(Rest).
perform_action(move(Direction)) :-
sokoban(SX, SY),
move(Direction, (SX, SY), (NX, NY)),
retract(sokoban(SX, SY)),
assertz(sokoban(NX, NY)).
perform_action(push(Direction)) :-
sokoban(SX, SY),
findall((CX, CY), crate(CX, CY), Crates),
push(Direction, (SX, SY), Crates, (NX, NY), NewCrates),
% Sokoban should end up in the crate's original position, not the pushed position
retract(sokoban(SX, SY)),
retractall(crate(_, _)),
assertz(sokoban(NX, NY)),
forall(member((CX, CY), NewCrates), assertz(crate(CX, CY))).
display_map :-
map_bounds(MaxRow, MaxCol),
forall(between(0, MaxRow, Row), (
forall(between(0, MaxCol, Col), display_cell(Row, Col)),
nl
)).
display_cell(Row, Col) :-
( sokoban(Row, Col) -> write('S')
; crate(Row, Col), storage(Row, Col) -> write('c')
; crate(Row, Col) -> write('C')
; storage(Row, Col) -> write('X')
; wall(Row, Col) -> write('#')
; write(' ')
).
map_bounds(MaxRow, MaxCol) :-
findall(Row, (wall(Row, _); crate(Row, _); storage(Row, _); sokoban(Row, _)), Rows),
findall(Col, (wall(_, Col); crate(_, Col); storage(_, Col); sokoban(_, Col)), Cols),
max_list(Rows, MaxRow),
max_list(Cols, MaxCol).
% Import necessary libraries
:- use_module(library(readutil)).
:- dynamic wall/2, crate/2, storage/2, sokoban/2.
% --- Map Loading ---
load_map(File) :-
retractall(wall(_, _)),
retractall(crate(_, _)),
retractall(storage(_, _)),
retractall(sokoban(_, _)),
read_file_to_string(File, MapString, []),
split_string(MapString, "\n", "", Lines),
exclude(=(""), Lines, NonEmptyLines),
parse_lines(NonEmptyLines, 0).
parse_lines([], _).
parse_lines([Line | Rest], Row) :-
string_chars(Line, Chars),
assert_line(Chars, Row, 0),
NewRow is Row + 1,
parse_lines(Rest, NewRow).
assert_line([], _, _).
assert_line([Char | Rest], Row, Col) :-
( Char = '#' -> assertz(wall(Row, Col))
; Char = 'C' -> assertz(crate(Row, Col))
; Char = 'X' -> assertz(storage(Row, Col))
; Char = 'S' -> assertz(sokoban(Row, Col))
; Char = 'c' -> assertz(crate(Row, Col)), assertz(storage(Row, Col))
; Char = 's' -> assertz(sokoban(Row, Col)), assertz(storage(Row, Col))
; true
),
NextCol is Col + 1,
assert_line(Rest, Row, NextCol).
% --- Helper Predicates ---
valid_position(X, Y) :-
\+ wall(X, Y).
goal_state(Crates) :-
findall((X, Y), storage(X, Y), StoragePositions),
sort(Crates, SortedCrates),
sort(StoragePositions, SortedCrates),
sokoban_can_exit(Crates).
sokoban_can_exit(Crates) :-
sokoban(SX, SY),
findall(Direction, valid_action((SX, SY), Crates, _, _, move(Direction)), ValidMoves),
ValidMoves \= [].
sokoban_trapped(Sokoban, Crates) :-
sokoban(SX, SY),
findall(Direction, valid_action((SX, SY), Crates, _, _, move(Direction)), Moves),
Moves == []. % Sokoban has no valid moves
state(Sokoban, Crates) :-
sokoban(SX, SY), Sokoban = (SX, SY),
findall((CX, CY), crate(CX, CY), Crates).
move(Direction, (SX, SY), (NX, NY)) :-
direction_delta(Direction, DX, DY),
NX is SX + DX,
NY is SY + DY,
valid_position(NX, NY),
\+ crate(NX, NY).
push(Direction, (SX, SY), Crates, (NX, NY), NewCrates) :-
direction_delta(Direction, DX, DY),
NX is SX + DX,
NY is SY + DY,
TX is NX + DX,
TY is NY + DY,
member((NX, NY), Crates),
valid_position(TX, TY),
\+ member((TX, TY), Crates),
select((NX, NY), Crates, CratesTmp),
append([(TX, TY)], CratesTmp, NewCrates).
direction_delta(up, -1, 0).
direction_delta(down, 1, 0).
direction_delta(left, 0, -1).
direction_delta(right, 0, 1).
% --- Deadlock Detection ---
deadlock(Crates) :-
member((X, Y), Crates),
\+ storage(X, Y),
( (wall(X-1, Y), wall(X, Y-1))
; (wall(X-1, Y), wall(X, Y+1))
; (wall(X+1, Y), wall(X, Y-1))
; (wall(X+1, Y), wall(X, Y+1))
).
count_deadlock_risks(Crates, Penalty) :-
findall(1, (member((X, Y), Crates), is_deadlock_position((X, Y))), DeadlockPositions),
length(DeadlockPositions, Penalty).
is_deadlock_position((X, Y)) :-
\+ storage(X, Y),
((wall(X-1, Y), wall(X, Y-1));
(wall(X-1, Y), wall(X, Y+1));
(wall(X+1, Y), wall(X, Y-1));
(wall(X+1, Y), wall(X, Y+1))).
% --- BFS Solver ---
solve(File) :-
load_map(File),
state(Sokoban, Crates),
bfs([(Sokoban, Crates, [])], [], [], Solution),
reverse(Solution, OrderedSolution),
write("Solution: "), nl, write(OrderedSolution), nl,
animate_solution(OrderedSolution).
bfs([], _, _, _) :-
write("No solution found."), nl, fail.
bfs([(Sokoban, Crates, Path) | _], _, _, Path) :-
write("Current Sokoban: "), write(Sokoban), nl,
write("Current Crates: "), write(Crates), nl,
write("Current Path: "), write(Path), nl,
goal_state(Crates),
\+ deadlock(Crates),
!.
bfs([(Sokoban, Crates, Path) | Rest], Visited, Explored, Solution) :-
findall(
(NextSokoban, NextCrates, [Action | Path]),
(valid_action(Sokoban, Crates, NextSokoban, NextCrates, Action),
\+ member((NextSokoban, NextCrates), Visited),
\+ member((NextSokoban, NextCrates), Explored),
\+ deadlock(NextCrates),
sokoban_can_exit(NextCrates)),
NextStates
),
prioritize_states(NextStates, SortedStates),
append(Rest, SortedStates, Queue),
bfs(Queue, [(Sokoban, Crates) | Visited], [(Sokoban, Crates) | Explored], Solution).
valid_action(Sokoban, Crates, NextSokoban, Crates, move(Direction)) :-
move(Direction, Sokoban, NextSokoban),
\+ member(NextSokoban, Crates). % Sokoban cannot move into a crate's position
valid_action(Sokoban, Crates, NextSokoban, NextCrates, push(Direction)) :-
push(Direction, Sokoban, Crates, NextSokoban, NextCrates).
% --- Prioritize States ---
prioritize_states(States, SortedStates) :-
maplist(score_state, States, ScoredStates),
sort(2, @=<, ScoredStates, SortedScoredStates),
maplist(remove_score, SortedScoredStates, SortedStates).
score_state((Sokoban, Crates, Path), ((Sokoban, Crates, Path), Score)) :-
findall(Distance, (member(Crate, Crates), crate_to_storage_distance(Crate, Distance)), CrateDistances),
sum_list(CrateDistances, TotalCrateToStorageDistance),
findall(Distance, (member(Crate, Crates), manhattan_distance(Sokoban, Crate, Distance)), SokobanDistances),
min_list(SokobanDistances, SokobanToClosestCrateDistance),
count_deadlock_risks(Crates, DeadlockPenalty),
Score is TotalCrateToStorageDistance * 10 + SokobanToClosestCrateDistance + DeadlockPenalty.
remove_score(((Sokoban, Crates, Path), _), (Sokoban, Crates, Path)).
% --- Distance Calculation Helpers ---
crate_to_storage_distance((CX, CY), Distance) :-
findall(D, (storage(SX, SY), manhattan_distance((CX, CY), (SX, SY), D)), Distances),
min_list(Distances, Distance).
manhattan_distance((X1, Y1), (X2, Y2), Distance) :-
Distance is abs(X1 - X2) + abs(Y1 - Y2).
% --- Visualization ---
animate_solution([]).
animate_solution([Action | Rest]) :-
write('Action: '), write(Action), nl,
perform_action(Action),
display_map,
sleep(0.5),
animate_solution(Rest).
perform_action(move(Direction)) :-
sokoban(SX, SY),
move(Direction, (SX, SY), (NX, NY)),
retract(sokoban(SX, SY)),
assertz(sokoban(NX, NY)).
perform_action(push(Direction)) :-
sokoban(SX, SY),
findall((CX, CY), crate(CX, CY), Crates),
push(Direction, (SX, SY), Crates, (NX, NY), NewCrates),
% Sokoban should end up in the crate's original position, not the pushed position
retract(sokoban(SX, SY)),
retractall(crate(_, _)),
assertz(sokoban(NX, NY)),
forall(member((CX, CY), NewCrates), assertz(crate(CX, CY))).
display_map :-
map_bounds(MaxRow, MaxCol),
forall(between(0, MaxRow, Row), (
forall(between(0, MaxCol, Col), display_cell(Row, Col)),
nl
)).
display_cell(Row, Col) :-
( sokoban(Row, Col) -> write('S')
; crate(Row, Col), storage(Row, Col) -> write('c')
; crate(Row, Col) -> write('C')
; storage(Row, Col) -> write('X')
; wall(Row, Col) -> write('#')
; write(' ')
).
map_bounds(MaxRow, MaxCol) :-
findall(Row, (wall(Row, _); crate(Row, _); storage(Row, _); sokoban(Row, _)), Rows),
findall(Col, (wall(_, Col); crate(_, Col); storage(_, Col); sokoban(_, Col)), Cols),
max_list(Rows, MaxRow),
max_list(Cols, MaxCol).