我有一个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;
}
所以所有这些，我有一个Quadtree的房间，这些房间已经或没有向上，向下，左和向右退出。
现在的目标是创建一个可以从一个房间到另一个房间（来自其坐标）的函数（如果存在），问题是我看不到在OCAML中如何做...无论如何，谢谢您的时间，祝您有美好的一天。
编辑：为了澄清，我是定义类型的人，可以在需要时更改它们。另外，我尝试实现Dijkstra的算法（来自Wikipedia的伪代码），但对这两个图表非常不熟悉，OCAML的数组和列表和列表非常不熟悉。确切地说，我的问题 - 我认为 - 我无法修改函数中的变量，例如在Wikipedia的伪代码中，在此行中：
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
如何在" for"循环之外修改区域和上一条段？我可以使用循环吗？还是更简单/更好地使用递归功能？
我也应该清楚地表明，迷宫是"定向"，这意味着能够从A房间到B房间，这并不意味着您可以从B房间到A房间A。
编辑2：一开始我应该澄清一下，对不起：Quadtree遵循以下规则：
| 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
)
)
)
)
;;
，但它给了我一个堆叠的溢出。经过一些研究后，似乎"包含_exit a"的行似乎永远不会真实，因此路线永远不会返回，并且循环！
有什么想法为什么？问题是我的 contains_exit 函数吗？
编辑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
[]
)
)
)
)
;;
有时会有时起作用...但是有时它会挡住，并且从一个房间到下面的一个房间，然后再次向上移动...我不明白为什么！？
如果您想尝试整个程序，则是：链接
然后您可以去做一些这样的事情：
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)（您可以制作一个添加函数以确保此属性）。
然后，您可以通过从末端探索的树，并获得最小的重量路径，然后结束起点。（它的重量与在相同条件下经过相同路径的重量相同（因为您从一开始就探索树，但从当时的结束来计算路径）。
此代码没有考虑到通过门的可能性，但这只是一项添加的检查，因为已经正确地将穿过树的方式定向了。
我让您完成并更正代码。
希望它对您有帮助。