从前的一个A*

烁灵 posted @ 2015年3月17日 22:53 in Ruby with tags A* 寻路 练习 , 1441 阅读

以前的一个a*练习，搬过来凑个数……

A*算法描述见这篇博文

ruby代码：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#encoding=utf-8
MAP = [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 1, 0, 1, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],      
      ]    
class Point
    attr_accessor       :x
    attr_accessor       :y
    attr_accessor       :g
    attr_accessor       :h
    attr_accessor       :f
    attr_accessor       :parent
    def initialize(x, y, parent)
        self.x = x
        self.y = y
        self.parent = parent
    end
    def to_s
        "#{super.to_s}, #{[self.x, self.y, self.g, self.h, self.f]}"
    end
end
 
$open = {}
$close = {}
 
def find(sx, sy, ex, ey)
    startP = Point.new(sx, sy, nil)
    startP.g = 0
    pos = startP
    while (!$open[[ex, ey]]) do
        dealAround(pos, ex, ey) # 检查周围元素，计算f
        pos = getMinFPos
    end
    pos = $open[[ex, ey]]
    path = []
    while (pos.parent) do
        path << [pos.x, pos.y]
        pos = pos.parent
    end
    path << [pos.x, pos.y]
    for y in 0...MAP.size
        for x in 0...MAP[0].size
            print (path.include?([x, y])) ? "☆" : (MAP[y][x] == 0 ? "□" : "■")
        end
        print "\r\n"
    end
    p path
end
def getMinFPos
    return nil if $open.size < 1
    minG = $open.values[0].g
    minGPos = $open.values[0]
    $open.values.each{|pos|
        if minG > pos.g
            minG = pos.g
            minGPos = pos
        end
    }
    return minGPos
end
def dealAround(pos, endx, endy)
    # 将pos加入close列表
    $close[[pos.x, pos.y]] = pos   
    # 将pos从open列表中移出
    $open.delete([pos.x, pos.y])
    # 检查周围元素
    [[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]].each{|posOffset|
        # 跳过边界
        next if pos.x + posOffset[0] < 0 or pos.y + posOffset[1] < 0 or pos.x + posOffset[0] > MAP[0].size - 1 or pos.y + posOffset[1] > MAP.size - 1
        # 跳过不可通行的方块
        next if MAP[pos.y + posOffset[1]][pos.x + posOffset[0]] != 0
        # 跳过close列表
        next if $close[[pos.x + posOffset[0], pos.y + posOffset[1]]]
         
        newPos = Point.new(pos.x + posOffset[0], pos.y + posOffset[1], pos)
        # 计算g
        if posOffset[0].abs + posOffset[1].abs == 2 # 斜向
            newPos.g = pos.g + 14
        else
            newPos.g = pos.g + 10
        end
        # 计算h
        newPos.h = (endx - newPos.x).abs * 10 + (endy - newPos.y).abs * 10
        # 计算f
        newPos.f = newPos.g + newPos.h
        # 添加到open列表
        if $open[[newPos.x, newPos.y]] # 已存在
            thePos = $open[[newPos.x, newPos.y]]   
            tempG = ((thePos.x - pos.x).abs + (thePos.y - pos.y).abs == 2) ? (pos.g + 14) : (pos.g + 10)
            if tempG < thePos.g  # 当前节点使g更小
                thePos.g = tempG
                thePos.f = tempG + thePos.h
                thePos.parent = pos # 修改父节点为当前节点
            end
        else    # 不存在
            $open[[newPos.x, newPos.y]] = newPos
        end
    }
end
 
find(0, 0, 7, 7)

 

Small_feed 评论 (2)
1
[回复]
Avatar_small
TNDGE Plus One Previ 说:
2022年8月22日 02:05

This board oversees a large number of schools in the state of Tamil Nadu, and it makes every effort to give its pupils access to a top-notch education. This board also held 11th-class exams during the current academic year in the state of Tamil Nadu, and all students who registered for those exams are currently awaiting the TN +1 Important Question Paper 2023. TNDGE Plus One Previous Paper 2023 The Directorate of Government Examinations, Tamil Nadu, released the TN 11th Question Paper 2023 for these examinations in May. Approximately 88.1% of the pupils that participated in the tests were successful.

2
[回复]
Avatar_small
Matthew Wade 说:
2025年3月26日 02:26

Wow! This could be one particular of the most helpful blogs We’ve ever arrive across on this subject. Actually Excellent. I am also an expert in this topic therefore I can understand your effort. 바카라사이트추천


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter