从前的一个A*

发表于 分类于 阅读次数： Disqus：

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

A*算法描述见这篇博文

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)

效果

预览图