recursion - Prolog maze solving algorithm -


i want implement maze solving algorithm in prolog. therefore searched maze solving algorithms , found following: http://www.cs.bu.edu/teaching/alg/maze/

find-path(x, y):

if (x,y outside maze) return false if (x,y goal) return true if (x,y not open) return false mark x,y part of solution path if (find-path(north of x,y) == true) return true if (find-path(east of x,y) == true) return true if (find-path(south of x,y) == true) return true if (find-path(west of x,y) == true) return true unmark x,y part of solution path return false

i build matrix in prolog, represents maze , 0 open , 1 wall, example (starting position (2|1) , goal located @ (4|1)):

11111 10001 10101

further more defined clause named mazedataat(coord_x, coord_y, mazedata, result), gives me value of matrix on position.

so far. have problem implementing algorithm in prolog. tried "the dirty way" (translate 1 one use of nested if statements), escalated complexity , don't think it's way in prolog.

so tried this:

isnotgoal(x, y) :-      x = 19, y = 2.  notopen(x, y, mazedata) :-     mazedataat(x, y, mazedata, 1).   findpath(x, y, mazedata) :-      isnotgoal(x, y),     notopen(x, y, mazedata),     increase(y, y_new),     findpath(x, y_new, mazedata),     increase(x, x_new),     findpath(x_new, y, mazedata),     decrease(y, y_new),     findpath(x, y_new, mazedata),     decrease(x, x_new),     findpath(x, y_new, mazedata).

but attempt didn't work expected.

actually, correct prolog implementation of algorithm above? how can see if approach finds path through maze? therefore how can record path or solution path (what done marking / unmarking path in algorithm above)?

thank help!

//update

thanks answers! adopted more prolog solution (see here) solve problem. have:

d([2,1], [2,2]). d([2,2], [1,2]). d([2,2], [2,3]).  go(from, to, path) :- go(from, to, [], path).  go(p, p, t, t). go(p1, p2, t, nt) :-     (d(p1, p3) ; d(p3, p2)),     \+ member(p3, t),     go(p3, p2, [p3|t], nt).

so far, works. , think understand why prolog way better. have small problem left.

i want knowledge base "dynamic". can't define edges every single waypoint in maze. therefore wrote clause named is_adjacent([x1, y1], [x2, y2]) true when [x1, y1] neighbor of [x2, y2].

i have list waypoints = [[2, 1], [2, 2]| ...] contains possible waypoints in maze.

now question: how can use make knowledge base "dynamic"? can use in go clause finding path?

thanks help!

//update 2

ok, got waypoints facts:

w(2, 1). w(2, 2). ...

i took solution boris in 1 of answers:

d(x0, y0, x , y) :-     w(x0, y0),     next_w(x0, y0, x, y),     w(x, y).  next_w(x0, y0, x0, y) :- y y0 + 1. next_w(x0, y0, x0, y) :- y y0 - 1. next_w(x0, y0, x, y0) :- x x0 + 1. next_w(x0, y0, x, y0) :- x x0 - 1.

after that, updated go clause, fits:

go(x1, y1, x2, y2, path) :- go(x1, y1, x2, y2, [], path).  go(x, y, x, y, t, t). go(x1, y1, x2, y2, t, nt) :-    (d(x1, y1, x3, y3) ; d(x3, y3, x1, y1)), \+ member([x3, y3], t), go(x3, y3, x2, y2, [[x3, y3]|t], nt).

but if try ask go(2, 1, 19, 2, r) prolog enters infinite loop. if try easier go(2, 1, 3, 8, r) works , solution path in r.

what doing wrong? did forget?

(this answer uses same path finding algorithm this answer)

edit 2

indeed, if input cells of rectangular matrix not walls, need somehow translate rules of kind "you can b". if waypoints then:

w(2,1). w(2,2).

etc, can translate algorithm pointed prolog rule this:

% possible move (x0,y0) (x,y) d(x0,y0,x,y) :-     w(x0,x0), % can skip check if know sure               % starting point valid waypoint               % or if want able start inside               % wall :)     next_w(x0,y0,x,y),     w(x,y). % neighboring waypoints next_w(x0,y0,x0,y) :- y y0+1. % go guess next_w(x0,y0,x0,y) :- y y0-1. % go down next_w(x0,y0,x,y0) :- x x0+1. % go left next_w(x0,y0,x,y0) :- x x0-1. % go right

note 2 things:

  1. i using 4-argument rule possible moves square (so adjust accordingly)
  2. the magic happens in next_w. when d called, uses next_w generate 4 possible neighbor squares (assuming can go up/down/left/right) , checks whether square indeed waypoint. not need check both ways more.

another edit: full code

w(0,0). w(0,1). w(1,1). w(2,1). w(3,1). w(4,1). w(5,1).         w(1,2).         w(3,2).         w(5,2).         w(1,3).         w(3,3).         w(5,3). w(0,4). w(1,4). w(2,4).         w(4,4). w(5,4).                 w(2,5). w(3,5). w(4,5).  d(x0,y0,x,y) :- next_w(x0,y0,x,y), w(x,y). next_w(x0,y0,x0,y) :- y y0+1. next_w(x0,y0,x,y0) :- x x0+1. next_w(x0,y0,x0,y) :- y y0-1. next_w(x0,y0,x,y0) :- x x0-1.  go(x,y,x,y,path,path). go(x0,y0,x,y,sofar,path) :-     d(x0,y0,x1,y1),     \+ memberchk( w(x1,y1), sofar ),     go(x1,y1,x,y,[w(x1,y1)|sofar],path).

you can call with

? go(0,0,5,4,[],path).

and should 2 possible solutions.

in other words, think problem semicolon; no longer necessary, because explicitly create possible moves.


Comments

Post a Comment

Popular posts from this blog

Why does Ruby on Rails generate add a blank line to the end of a file? -

running rails generate controller foo home results in: class foocontroller < application controller def home end end (there's nothing on line in actual file, blank line) is there purpose blank line? it's common use newline indicate end of line, last line. many editors (like vi, use) add in newline silently. consensus text files (especially in unix world) should end in newline, , there have been problems historically if wasn't present. why should text files end newline? the tool used count lines in file "wc" counts newlines in file, without trailing newline show 3 instead of 4. it improves readability of templates used in generator. consider: https://github.com/rails/rails/blob/master/railties/lib/rails/generators/rails/controller/templates/controller.rb to remove trailing newline, template have last line of: end<% end -%> instead of: end <% end -%> that seems less readable me. the discussion below refers ...
Read more

keyboard - Smiles and long press feature in Android -

i've created android keyboard. how add features inserting smilies, , using long keypresses display symbols? to create long-press behavior allows select several options pop-up menu, follow guide (specifically pop-up menu section): http://developer.android.com/guide/topics/ui/menus.html smileys (also known emoticons) combination of keys, understood programs , parsed same way. have do, when clicks smiley face on keyboard, simulate pressing of key combination matching emoticon. example, when clicks smiley, should simulate key presses ':' , ')' :). here's list of emoticons: http://en.wikipedia.org/wiki/list_of_emoticons
Read more

node.js - Bad Request - node js ajax post -

i'm using express 3.0 , node v0.11.0. have button submits form , i'm using ajax post data json object node server. client code is: $('#contact').submit(function(e) { console.log('submit called'); var formdata = json.stringify($('form').serializeobject()); console.log(formdata); $.ajax({ url: "http://localhost:3000/savedata/", type: "post", datatype: 'json', data: {objectdata: formdata}, contenttype: "application/json", complete: function() { console.log('process complete'); }, success: function(data) { console.log('process sucess'); }, error: function() { console.log('process error'); }, }); return false; }); then on server: var express = require('express'); var app = express(); app.set('views', __dirname + '/views'); app.set('view engine', 'jade'); app.use(express.bodyparser());...
Read more