高中 Scratch 课件：19-20-迷宫游戏

本节目标这节课即我们即将学习迷宫的绘制数字地图的使用路径的自动搜索本节目标这节课即我们即将学习走迷宫17-1迷宫程序界面如右图所示点击“重建地图”，地图被擦除，用户通过点击鼠标或按着鼠标左键拖动鼠标来绘制地图绿色代表通道，小猫只能在通道上行走，不能走到白色的区域上面去点击“探索迷宫”，小猫自动在绘制完成的地图上寻找路径，直到吃到鱼或发现没有通到鱼的路径可走为止走迷宫17-1迷宫程序界面如右图所示走迷宫17-2程序中有5个角色，分别是小猫汤姆、绘制通道的绿色方块、“重建地图”按钮、鱼和“探索迷宫”按钮走迷宫17-2程序中有5个角色，分别是小猫汤姆、绘制通道的走迷宫17-3地图绘制原理将屏幕划出一个宽420高300的区域，然后将此区域分为宽30高30的小方格。这样的小方格有14列，10行，共计140个。“通道”角色是一个宽30高30的绿色方块。绘制地图时，判断鼠标按下时鼠标光标所处的位置落于哪个小方格中，然后将“通道”角色移至该方块的左下角，使用“图章”方法绘制一个方格走迷宫17-3地图绘制原理走迷宫17-4地图绘制原理为了易于程序判断，除了在屏幕上绘制地图，还要保存一幅“数字地图”。建立链表map，插入140个0，代表空白地图。链表map的每一个元素，代表一个小方格。元素值为1时，代表方格为绿色通道。元素值为0时，代表方格为白色障碍。走迷宫17-4地图绘制原理走迷宫17-5地图绘制原理链表map第1-14个元素代表第一行方格，第15-28个元素代表第二行方格，依此类推。绘制地图时，除了根据鼠标光标位置绘制“通道”外，也要将相应方格对应的链表元素设置为1。数字地图如下图所示。第x行y列方格在链表中对应的元素是(x-1)*14+y，比如第2行2列方格在链表中对应的元素是(2-1)*14+2=16，其值是0，代表一个空白的障碍方格走迷宫17-5地图绘制原理走迷宫17-6地图绘制原理屏幕上的地图是显示给人看的，叫“视图”数字地图是程序判断、运行的依据，叫“数据”或“文档”如果希望程序运行效果和人的期望相同，则数字地图中数据所表达的含义必须和“视图”显示的效果一致走迷宫17-6地图绘制原理走迷宫17-7地图绘制原理当点击“重建地图”按钮后，执行右面代码作用是将小猫探索迷宫的标志变量Run设为0，小猫停止探索，删除地图map链表内容，重新插入140个0，清除界面全部画笔绘制内容，得到一个空白的地图。播放声音Meow目的是告诉用户按钮已经被点中走迷宫17-7地图绘制原理01234567891011121398765432100123456走迷宫17-8地图绘制原理右面代码的作用是绘制地图当按下鼠标时，根据鼠标位置计算应绘制哪一个方格（鼠标的x坐标-鼠标的x坐标除以30的余数）/30这是为了求得鼠标所在方格的整数列走迷宫17-8地图绘制原理走迷宫17-9地图绘制原理因为屏幕左边界x坐标为-240，为使求得列数为从左到右自0（第一列标号为0）开始，统一加8同样的原因，计算鼠标所在方格行数时因为鼠标下边界y坐标为-180，统一加6走迷宫17-9地图绘制原理走迷宫17-10当点击“探索迷宫”按钮后，执行右面代码作用是将pass链表初始化为140个0，表示地图上所有方格都没有探索过然后将Run设置为1，允许探索迷宫程序运行广播事件“探索迷宫”，触发探索迷宫程序运行走迷宫17-10当点击“探索迷宫”按钮后，执行右面代码走迷宫17-11角色“鱼”的代码作用是将小鱼移到地图右上角的方格，即第10行，第14列的方格，方格的编号从0开始，即行为0-9，列为0-13走迷宫17-11角色“鱼”的代码走迷宫17-12路径搜索算法变量cat_x，cat_y用于记录小猫当前所在方格的位置，cat_x表示所在列（0-13），cat_y表示所在行（0-9）LastStep表示小猫上一步所在的方格，用方格在map列表中的索引表示NextStep是一临时变量，表示小猫下一步可能进入的方格，用方格在map列表中的索引表示Direction代表小猫的前进方向，1-上，2-下，3-左，4-右走迷宫17-12路径搜索算法走迷宫17-13路径搜索算法链表map表示地图链表pass用于记录小猫探索过的方格，其结构和map相同，大小被初始化为140，每个元素对应地图上的一个方格曾经走过的方格对应元素设为1，一次也没有走过的方格对应元素设为0Path代表小猫从起点（左下角方格）为了达到终点（鱼所在右上角方格）探索走过的路径，其大小动态变化，小猫每走一步，经过的方格位置就被插入链表Path的头部（第一个元素）走迷宫17-13路径搜索算法走迷宫17-14路径搜索算法1.根据小猫当前位置，假设一个前进方向，比如向上，计算NextStep2.判断NextStep进入方格如果没有超越边界，且从未探索过，且不是来时刚走过的方格，则此假设方向可行，小猫进入NextStep所对应方格，将pass中NextStep对应元素设置为1，标志此方格已经走过，将NextStep添加到Path头部，路径向前延伸3.如果上述条件不成立，则判断下一个方向4.如果所有方向都不可行，说明此路不通。从Path中取出上一步走过的方格，回退到此方格，返回到步骤(1)。如果Path中已经为空，说明已经探索过所有可能达到的方格，仍然无法到达终点。探索过程结束，说“无路可走，游戏结束！”走迷宫17-14路径搜索算法19543212687101113Path:19543212687101113Path:走迷宫17-15具体程序实现时，先决定前进的方向，然后再前进，探索初始化及判断向上一步是否可行的代码如右走迷宫17-15具体程序实现时，先决定前进的方向，然后再走迷宫17-16其他方向的判断，同向上的判断方式相同，下面是所有方向都走不通后的处理代码走迷宫17-16其他方向的判断，同向上的判断方式相同，下走迷宫17-17根据前面决定的方向，前进一步的代码如下走迷宫17-17根据前面决定的方向，前进一步的代码如下练习编写坦克大战游戏链表实现数字地图，用0代表通道，1代表砖墙，2代表草地，3代表石墙等等自己绘制或上网查找坦克、砖墙、草地、石墙等图片，统一大小，作为构造地图的素材可开发两个程序，一个是地图编辑器，专门用作编辑地图使用；另一个是游戏程序，实现人机对战人控制坦克，保卫自己的基地，电脑进攻，消灭所有电脑坦克，基地不被损毁则可过关练习编写坦克大战游戏总结这节课我们学习了迷宫的绘制数字地图的使用路径的自动搜索总结这节课我们学习了本节目标这节课即我们即将学习迷宫的绘制数字地图的使用路径的自动搜索本节目标这节课即我们即将学习走迷宫17-1迷宫程序界面如右图所示点击“重建地图”，地图被擦除，用户通过点击鼠标或按着鼠标左键拖动鼠标来绘制地图绿色代表通道，小猫只能在通道上行走，不能走到白色的区域上面去点击“探索迷宫”，小猫自动在绘制完成的地图上寻找路径，直到吃到鱼或发现没有通到鱼的路径可走为止走迷宫17-1迷宫程序界面如右图所示走迷宫17-2程序中有5个角色，分别是小猫汤姆、绘制通道的绿色方块、“重建地图”按钮、鱼和“探索迷宫”按钮走迷宫17-2程序中有5个角色，分别是小猫汤姆、绘制通道的走迷宫17-3地图绘制原理将屏幕划出一个宽420高300的区域，然后将此区域分为宽30高30的小方格。这样的小方格有14列，10行，共计140个。“通道”角色是一个宽30高30的绿色方块。绘制地图时，判断鼠标按下时鼠标光标所处的位置落于哪个小方格中，然后将“通道”角色移至该方块的左下角，使用“图章”方法绘制一个方格走迷宫17-3地图绘制原理走迷宫17-4地图绘制原理为了易于程序判断，除了在屏幕上绘制地图，还要保存一幅“数字地图”。建立链表map，插入140个0，代表空白地图。链表map的每一个元素，代表一个小方格。元素值为1时，代表方格为绿色通道。元素值为0时，代表方格为白色障碍。走迷宫17-4地图绘制原理走迷宫17-5地图绘制原理链表map第1-14个元素代表第一行方格，第15-28个元素代表第二行方格，依此类推。绘制地图时，除了根据鼠标光标位置绘制“通道”外，也要将相应方格对应的链表元素设置为1。数字地图如下图所示。第x行y列方格在链表中对应的元素是(x-1)*14+y，比如第2行2列方格在链表中对应的元素是(2-1)*14+2=16，其值是0，代表一个空白的障碍方格走迷宫17-5地图绘制原理走迷宫17-6地图绘制原理屏幕上的地图是显示给人看的，叫“视图”数字地图是程序判断、运行的依据，叫“数据”或“文档”如果希望程序运行效果和人的期望相同，则数字地图中数据所表达的含义必须和“视图”显示的效果一致走迷宫17-6地图绘制原理走迷宫17-7地图绘制原理当点击“重建地图”按钮后，执行右面代码作用是将小猫探索迷宫的标志变量Run设为0，小猫停止探索，删除地图map链表内容，重新插入140个0，清除界面全部画笔绘制内容，得到一个空白的地图。播放声音Meow目的是告诉用户按钮已经被点中走迷宫17-7地图绘制原理01234567891011121398765432100123456走迷宫17-8地图绘制原理右面代码的作用是绘制地图当按下鼠标时，根据鼠标位置计算应绘制哪一个方格（鼠标的x坐标-鼠标的x坐标除以30的余数）/30这是为了求得鼠标所在方格的整数列走迷宫17-8地图绘制原理走迷宫17-9地图绘制原理因为屏幕左边界x坐标为-240，为使求得列数为从左到右自0（第一列标号为0）开始，统一加8同样的原因，计算鼠标所在方格行数时因为鼠标下边界y坐标为-180，统一加6走迷宫17-9地图绘制原理走迷宫17-10当点击“探索迷宫”按钮后，执行右面代码作用是将pass链表初始化为140个0，表示地图上所有方格都没有探索过然后将Run设置为1，允许探索迷宫程序运行广播事件“探索迷宫”，触发探索迷宫程序运行走迷宫17-10当点击“探索迷宫”按钮后，执行右面代码走迷宫17-11角色“鱼”的代码作用是将小鱼移到地图右上角的方格，即第10行，第14列的方格，方格的编号从0开始，即行为0-9，列为0-13走迷宫17-11角色“鱼”的代码走迷宫17-12路径搜索算法变量cat_x，cat_y用于记录小猫当前所在方格的位置，cat_x表示所在列（0-13），cat_y表示所在行（0-9）LastStep表示小猫上一步所在的方格，用方格在map列表中的索引表示NextStep是一临时变量，表示小猫下一步可能进入的方格，用方格在map列表中的索引表示Direction代表小猫的前进方向，1-上，2-下，3-左，4-右走迷宫17-12路径搜索算法走迷宫17-13路径搜索算法链表map表示地图链表pass用于记录小猫探索过的方格，其结构和map相同，大小被初始化为140，每个元素对应地图上的一个方格曾经走过的方格对应元素设为1，一次也没有走过的方格对应元素设为0Path代表小猫从起点（左下角方格）为了达到终点（鱼所在右上角方格）探索走过的路径，其大小动态变化，小猫每走一步，经过的方格位置就被插入链表Path的头部（第一个元素）走迷宫17-13路径搜索算法走迷宫17-14路径搜索算法1.根据小猫当前位置，假设一个前进方向，比如向上，计算NextStep2.判断NextStep进入方格如果没有超越边界，且从未探索过，且不是来时刚走过的方格，则此假设方向可行，小猫进入NextStep所对应方格，将pass中NextStep对应元素设置为1，标志此方格已经走过，将NextStep添加到Path头部，路径向前延伸3.如果上述条件不成立，则判断下一个方向4.如果所有方向都不可行，说明此路不通。从Pat