OCaml Pathfinding в лабиринте Quadtree

Question

У меня есть тип quadTree, определенный следующим образом:

type 'a quadtree = 
| Empty 
| Leaf of 'a 
| Node of 'a quadtree * 'a quadtree * 'a quadtree * 'a quadtree;;

Комнаты, определенные как

type room = {
n : bool;
e : bool;
s : bool;
w : bool;
ps : coord;
exit : bool
}

Координаты, определенные как

type coord = {
x : int;
y : int;
}

Так что TLDR всего этого, У меня есть Quadtree комнат, которые имеют или не имеют выходов вверх, вниз, влево и вправо.

Теперь цель состоит в том, чтобы создать функцию, которая найдет путь (если он существует)из одной комнаты в другую (из ее координат) проблема в том, что я не вижу, как это сделать в OCaml ... В любом случае, спасибо за ваше время, хорошего дня.

Редактировать: Чтобы прояснить, именно я определяю типы и могу изменять их при необходимости.Кроме того, я попытался реализовать алгоритм Дейкстры (из псевдокода Википедии), но совершенно незнаком с обоими графиками, а также массивами и списками OCaml.Точнее говоря, моя проблема - я думаю - связана с тем, что я не могу изменять переменные в функции, например, в псевдокоде Википедии, в этой строке:

u ← Q.extract_min()                    // Remove and return best vertex

Я вижукак удалить лучшую вершину, и я вижу, как ее вернуть, но не обе одновременно.Или вот:

for each neighbor v of u:           // where v is still in Q.
    alt ← dist[u] + length(u, v)
    if alt < dist[v]:               // A shorter path to v has been found
        dist[v] ← alt 
        prev[v] ← u

Как изменить dist и prev вне цикла for?Могу ли я использовать цикл for или проще / лучше использовать рекурсивную функцию?

Также я должен пояснить, что лабиринт является "направленным", что означает, что возможность перехода из комнаты A в комнату B делаетне значит, что вы сможете перейти из комнаты B в комнату A.

Edit 2: Я должен был уточнить это в начале, извините: квадриследует этому правилу:

| Node of North West * North East * South West * South East

Редактировать 3: Хорошо, смена плана, оказывается, я делал очень глупо,Мне не нужно искать дорогу в определенную комнату, просто к выходу.Итак, я попробовал это:

let rec contains_exit = function
    | [] -> false
    | e::l' when (getCell e.x e.y maze).exit -> true
    | e::l' when (getCell e.x e.y maze).exit = false -> contains_exit l'
;;

let rec find_exit start way =
    if is_exit start then 
        way
    else
    (let a = find_exit (northp start) way@[start] in
    if contains_exit a then
        way
        else
        (
        let b = find_exit (eastp start) way@[start] in
        if contains_exit b then
            way
            else 
            (
        let c = find_exit (southp start) way@[start] in
        if contains_exit c then
            way
                else
                (
            let d = find_exit (westp start) way@[start] in
            if contains_exit d then
                way
                    else
                        way
                )
            )
        )
    )
;;

Но это дает мне переполнение стека.После небольшого исследования кажется, что строка «содержит_ выход а» никогда не верна, поэтому путь никогда не возвращается и он не зацикливается!

Есть идеи, почему это так?Проблема в том, что моя функция содержит_выход ?

Редактировать 4: Закончилась ли эта функция:

let rec find_exit start way =
    sleep 50000000;
    let r = (Random.int 180) in
    set_color (rgb r r r);
    fill_rect (start.x * sizeCell + doorWidth * 2) (start.y * sizeCell + doorWidth * 2) (sizeCell - 4 * doorWidth) (sizeCell - 4 * doorWidth);
    if is_exit start then 
            way@[start]
    else
    (let a = if (getCell start.x start.y maze).n && ((mem (northp start) way) = false) then find_exit (northp start) way@[start] else [] in
    if a != [] then
        a
        else
        (
        let b = if (getCell start.x start.y maze).e && ((mem (eastp start) way) = false) then find_exit (eastp start) way@[start] else [] in
        if b != [] then
            b
            else 
            (
        let c = if (getCell start.x start.y maze).w && ((mem (westp start) way) = false) then find_exit (westp start) way@[start] else [] in
        if c != [] then
            c
                else
                (
            let d = if (getCell start.x start.y maze).s && ((mem (southp start) way) = false) then find_exit (southp start) way@[start] else [] in
            if d != [] then
                d
                    else
                        []
                )
            )
        )
    )
;;

itиногда работает ... Но иногда он блокируется и переходит из одной комнаты в нижнюю, затем снова вверх, затем снова вниз ... Я не понимаю почему!?

Если вы хотите попробовать весьпрограмма, вот она: ссылка

Answer 1

Затем вы можете перейти к такой вещи:

type 'a quadtree = 
| Empty 
| Leaf of 'a 
| Node of 'a * 'a quadtree * 'a quadtree * 'a quadtree * 'a quadtree;;

type room = {
n : bool;
e : bool;
s : bool;
w : bool;
ps : coord;
exit : bool
};;

type coord = {
x : int;
y : int;
};;

let rec treeForRoom(tree, room) = 
    match tree with
    | Empty -> Empty
    | Leaf l -> if l.ps == room.ps then l else Empty
    | Node (r, n, e, s, w) as node -> 
        if r == room 
        then  node
        else 
            match ((r.ps.x - room.ps.x), (r.ps.y - room.ps.y)) with
            | (0, n) -> if n > 0 then treeForRoom(w) else treeForRoom(e)
            | (n, 0) -> if n > 0 then treeForRoom(s) else treeForRoom(n)

(* Assuming the root of the tree is the room we start from *)
let rec searchPath(tree, r) = 
    match tree with
    | Empty -> (false, 0, [])
    | Leaf l -> if l == r then (true, 0) else (false, 0, [])
    | Node (r, n, e, s, w) as node -> 
       let pn = searchPath(n, r) 
       and pe = searchPath(e, r) 
       and ps = searchPath(s, r)
       and pw = searchPath(w, r)
    in
        find_best_path(p1, p2, p3, p4)

let find_best_path(p1, p2, p3, p4) = 
    match (p1, p2, p3, p4) with
    | ((false,_,_), (false,_,_), (false,_,_), (false,_,_)) -> (false, -1, [])
    | ((true, w, p), (false,_,_), (false,_,_), (false,_,_)) -> (true, w, p)
    | ((false,_,_), (true, w, p)), (false,_,_), (false,_,_)) -> (true, w, p)
    | ((false,_,_), (false,_,_), (true, w, p)), (false,_,_)) -> (true, w, p)
    | ((false,_,_), (false,_,_), (false,_,_),(true, w, p)) -> (true, w, p)
    | ((p1ok, p1w, p1p), (p2ok, p2w, p2p),(p3ok, p3w, p3p),(p4ok, p4w, p4p)) -> 
        if p1ok && p2ok && p3ok && p4ok
        then 
            min_weight([(p1ok, p1w, p1p), (p2ok, p2w, p2p),(p3ok, p3w, p3p),(p4ok, p4w, p4p)])
        else 
        ....

let rec min_weight(l) = 
    match l with
    | [] -> (false, -1, [])
    | [t] -> t 
    | [(to, tw, tp) as t::q] -> let (mo, mw, mp) as minw = min_weight(q) in 
        if tw < mw
        then
            t
        else
            minw

Я добавил корень в определение типа ('a* ...), чтобы я мог создать функцию, чтобы найти хорошее дерево для прохождения.Я также предполагаю, что дерево соблюдает следующее правило: (root, north room, east room, south room, west room) для каждого узла (вы можете сделать функцию добавления для обеспечения этого свойства).

Затем вы проходите дерево, исследуя его с конца и получая минимальноепуть веса для конца до начальной точки.(Это тот же вес, что и по тем же путям в тех же условиях (потому что вы исследуете дерево с самого начала, но вычисляете путь с этого конца)).

Этот код не учитывает возможность прохода через двери, но это просто проверка, которую нужно добавить, поскольку путь прохождения дерева уже правильно ориентирован.

Я позволю вам заполнить и исправить код.

Надеюсь, он вам поможет.