用golang写一个简单的游戏(四)

上回分析到了炸弹的数量与位置问题,得出了随机位置的最多炸弹数量,但炸弹数量看起来并不多,这使得路径十分随意,因此,炸弹数量我不想太少,直接自己手动定义了。其实还有个思路的,就是按照区域随机分配炸弹,比如每个5×5区域就随机分配一个炸弹,实现方式还有其他形式,不在这个问题上纠结了。我今天想实现一个功能,自动打印出从起点到终点的最短路径,以便在炸弹数量足够多的时候,很快得出一个答案。

一个m×n的地图,我们很容易知道最短路径是m+n-1。不过炸弹的设定,让这个最短路径发生了变化,炸弹的周围不能经过,所以可能出现以下这种情况:

这是炸弹足够多的时候会出现的情况,如果是炸弹比较少的话,其实并不会干扰到我们,我们很容易就可以走出一个最短路径,因为经过平移,我们知道,只要我们只要不往上不往左走,就是一条最短路径了。

但是炸弹足够多的话,就不能这么定义了,这干扰了我们的路径。我们前进的每一步可能是任意的三个方向,同时,最短路径可能有多条。当前我们在一个点上,要思考下个点走到哪去。我们到下个点也一样要做同样的思考。这就很明显是个递归的问题了。明白是个递归问题,我们就可以定义我们的路径是怎么走:

pointR, isStopR := components.NewPoint(rp, point, "right")
        pointD, isStopD := components.NewPoint(rp, point, "down")
                pointL, isStopL := components.NewPoint(rp, point, "left")
                pointU, isStopU := components.NewPoint(rp, point, "up")

每个点理论上都可能会有四个方向可以走,但为什么我前面说了是“三个”?因为有一个方向是你刚走过来的,比如你上个点是从右边来的,这时你再回到右边,那就走了回头路,这是没有意义的。

递归有时候是个解决问题的利器,但是比较难的点是让它停下来。我们要思考一下它的终止条件。

  1. 就是刚刚的回头路问题,走过的点是不允许回到的,回到了则代表这条路走不通,应该放弃。
    func HasDuplicatedPoint(p *Point) bool {
    _p := p
    x, y := _p.X, _p.Y
    for _p.LastPoint != nil {
        if _p.LastPoint.X == x && _p.LastPoint.Y == y {
            return true
        } else {
            _p = _p.LastPoint
        }
    }
    return false
    }
  2. 不能经过的点也不是下一步应该去的方向,比如边界、比如炸弹区域,走到了这一步说明此路不通。
    for _, v := range rp.BoomPosition {
        if x == v[0] && y == v[1] {
            return lastPoint, true
        }
    }
    for _, v := range rp.TrapPosition {
        if x == v[0] && y == v[1] {
            return lastPoint, true
        }
    }
  3. 到达终点,毫无疑问,这表示我们已经完成任务了。
    if rp.EndPoint[0] != point.X || rp.EndPoint[1] != point.Y {
       ……
    }

此时,我们已经具备了得到所有路径的条件,但是有个问题,我要的是最短路径,而递归,会把所有的路径都找出来。这个好办,我用一个map来存所有的路径,并从中找出一个路径最短的。问题至此解决。

有兴趣的话可以去看看代码: https://github.com/TomatoMr/boomboom.git

欢迎关注我的公众号:onepunchgo,给我留言。

欢迎关注我们的微信公众号,每天学习Go知识

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章