使用 Python 和 PyGame 的 A* 算法解决 8 拼图

Ghazanfar_Ali

4.32/5 (9投票s)

2012 年 4 月 13 日

CPOL

3分钟阅读

212460

4773

使用 Python 和 PyGame 实现 A* 算法来自动解决 8-Puzzle 问题。

下载 astart8puzzle.zip - 2.4 KB

介绍

8-Puzzle 是一个有趣的游戏，需要玩家一次移动一个方块来解决一个图片或一个特定的模式。在这篇文章中，我将向您展示如何编写一个智能程序，该程序可以使用 Python 和 PyGame 中的 A* 算法自动解决 8-Puzzle 问题。我们将使用数字模式（如图所示）作为最终状态，而不是图片。如果您需要了解 A* 算法理论或 8-Puzzle，请查阅维基百科。

背景

人工智能是使机器智能化的科学。为了使机器智能化，我们需要一些处理数据和环境的方法。人工智能中的一切都遵循算法。在基础层面，有一些简单但令人印象深刻的算法。A* 算法是人工智能的基本算法之一。A* 使用启发式函数来找到问题的解决方案。有关人工智能及其算法的更多信息，请阅读书籍“人工智能：一种现代方法”。

基本工作流程

手动解决 8-Puzzle 问题因人而异。为了通过计算机或人工智能解决这个问题，我们需要对它的工作原理有一个基本的了解才能获得目标节点。

以下是步骤：

获取场景的当前状态（指的是现实世界中的棋盘或游戏）。
找到可用的移动及其成本。
选择成本最低的移动并将其设置为当前状态。
检查它是否与目标状态匹配，如果是，则终止；如果不是，则转到步骤 1。

在代码中，我们的代理（程序）将寻找状态中的一个空位（'0'），然后寻找允许的且成本最低的移动。因此，它将朝着我们的最终状态（目标）前进。

使用代码

首先，您需要 Python 3.2 版本和一个兼容的 PyGame 库。有两个类。

A* 实现 (py8puzzle.py)。
模拟（需要 PyGame）(puzzler.py)。

A* 算法类是独立的。您可以使用它编写一段不需要 pyGame 的代码，或者您可以将其导入到另一个项目中。模拟文件是用 PyGame 编写的一个小游戏，用于解决该场景。你的互动将是最小的。只需运行该文件 (puzzler.py)。它将生成一个随机场景，然后只需单击窗口中的任意位置，程序就会尝试解决它。由于这是一个人工智能问题，因此预计某些最坏情况需要花费很长时间。通常，它花费的时间少于一分钟。

py8puzzle.py

让我们来看看代码。

首先使用构造函数初始化环境

import math,random
class puzzel:
    def __init__(self):
        #self.node=[]
        self.fronts=[]
        self.GoalNode=['1','2','3','4','5','6','7','8','0']
        self.StartNode=['1','2','3','4','5','6','7','8','0']
        self.PreviousNode=[]

正如您所看到的，起始节点和目标节点是相同的，而且它们都是一维的。我们将使用起始节点来创建要解决的场景。这是因为有很多场景是无法解决的。我只使用一维数组，而不是使用二维数组。在代码中，我以这样一种方式处理它，即它将做同样的事情。 “0”表示空格。

生成场景：

def shufler(self):
                
    while True:
        node=self.StartNode
        subNode=[]
        direct=random.randint(1,4)
        getZeroLocation=node.index('0')+1
        subNode.extend(node)
        boundry=self.boundries(getZeroLocation)
                
        if getZeroLocation+3<=9 and direct==1:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')+3]
            subNode[node.index('0')+3]=temp
            self.StartNode=subNode
            return
            
        elif getZeroLocation-3>=1 and direct==2:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')-3]
            subNode[node.index('0')-3]=temp
            self.StartNode=subNode
            return
                
        elif getZeroLocation-1>=boundry[0] and direct==3:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')-1]
            subNode[node.index('0')-1]=temp
            self.StartNode=subNode
            return
        
        elif getZeroLocation+1<=boundry[1] and direct==4:
            temp=subNode[node.index('0')]
            subNode[node.index('0')]=subNode[node.index('0')+1]
            subNode[node.index('0')+1]=temp
            self.StartNode=subNode
            return

启发式函数

我们将使用双重启发式函数，即错误放置的图块的数量以及错误放置的图块之间的距离。

def heruistic(self,node):
    herMisplaced=0
    herDist=0
    
    for i in range(9):
        if node[i]!=self.GoalNode[i]:
            herMisplaced +=1
    for i in node:
        herDist +=math.fabs(node.index(i)-self.GoalNode.index(i))
    
    totalHerst=herDist+herMisplaced
   
    node.append(totalHerst)
    return node

后继节点

要获得后继节点，程序将寻找空格和允许的移动，并将返回一个由可用移动及其启发式值组成的数组。

def sucessor(self,node=[]):
    subNode=[]
    getZeroLocation=node.index('0')+1
    subNode.extend(node)
    boundry=self.boundries(getZeroLocation)
	self.fronts=[]
            
    if getZeroLocation+3<=9:
        temp=subNode[node.index('0')]
        subNode[node.index('0')]=subNode[node.index('0')+3]
        subNode[node.index('0')+3]=temp
        self.fronts.append(self.heruistic(subNode))
        subNode=[]
        subNode.extend(node)
    if getZeroLocation-3>=1:
        temp=subNode[node.index('0')]
        subNode[node.index('0')]=subNode[node.index('0')-3]
        subNode[node.index('0')-3]=temp
        self.fronts.append(self.heruistic(subNode))
        subNode=[]
        subNode.extend(node)
    if getZeroLocation-1>=boundry[0]:
        temp=subNode[node.index('0')]
        subNode[node.index('0')]=subNode[node.index('0')-1]
        subNode[node.index('0')-1]=temp
        self.fronts.append(self.heruistic(subNode))
        subNode=[]
        subNode.extend(node)
    if getZeroLocation+1<=boundry[1]:
        temp=subNode[node.index('0')]
        subNode[node.index('0')]=subNode[node.index('0')+1]
        subNode[node.index('0')+1]=temp
        self.fronts.append(self.heruistic(subNode))
        subNode=[]
        subNode.extend(node)

选择下一个节点

要选择下一个节点，程序将寻找具有最小启发式的节点。该程序还将保存所选节点，并将每次查找此历史记录以确保不会启动冗余移动。

def getNextNode(self):
    nxNode=[]
    tNode=[]
    while True:
        hrCost=100000
        for i in self.fronts:
                if(i[-1]<hrCost):
                    hrCost=i[-1]
                    nxNode=i[0:-1]
                    tNode=i
        
        if tNode in self.PreviousNode and tNode in self.fronts:
            self.fronts.remove(tNode)
            self.PreviousNode.append(tNode)
            
        else:
            self.PreviousNode.append(tNode)
            return nxNode

puzzler.py

此类包含运行此算法的代码。您也可以使用 py8puzzle.py 中的 solve() 函数，而无需图形。

import pygame, sys, time
from pygame.locals import *
from py8puzzel import*

puzzle=puzzel() 
#puzzle.Solve()

pygame.init()
WINDOWWIDTH = 600
WINDOWHEIGHT = 600
BASICFONT = pygame.font.Font('freesansbold.ttf',50)
windowSurface = pygame.display.set_mode((WINDOWWIDTH, WINDOWHEIGHT), 0, 32)
pygame.display.set_caption('8 Puzzle')

BLACK = (0, 0, 0)
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)
WHITE=(255,255,255)
Text=(0,0,0)

blockTOP=0;
blockLEFT=0;
blocks=[]
blockNumber=1

for i in range(3):
    for j in range(3):
       
        if blockNumber>8:
            blocks.append({'rect':pygame.Rect(blockLEFT,blockTOP,99,99),'color':BLACK,'block':str(0)})
        else:
            blocks.append({'rect':pygame.Rect(blockLEFT,blockTOP,99,99),'color':GREEN,'block':str(blockNumber)})
        blockNumber+=1
        blockLEFT+=100
    blockTOP+=100
    blockLEFT=0

for b in blocks:        
        pygame.draw.rect(windowSurface, b['color'], b['rect'])
        textSurf = BASICFONT.render(b['block'], True,Text)
        textRect = textSurf.get_rect()
        textRect.center = b['rect'].left+50,b['rect'].top+50
        windowSurface.blit(textSurf, textRect)
pygame.display.update()
     
numShufles=50
evt=False  
while True:
    # check for the QUIT event
    for event in pygame.event.get():
        if event.type==MOUSEBUTTONDOWN and event.button==1:
            evt=True
            
    while numShufles>0:
        puzzle.shufler()
        puzzle.PreviousNode.extend(puzzle.StartNode)
        block=0
        for b in blocks:
            b['block']=str(puzzle.StartNode[block])
            block+=1
            
            if b['block']=='0':
                b['color']=BLACK
            else:
                b['color']=GREEN         
            pygame.draw.rect(windowSurface, b['color'], b['rect'])
            textSurf = BASICFONT.render(b['block'], True,Text)
            textRect = textSurf.get_rect()
            textRect.center = b['rect'].left+50,b['rect'].top+50
            windowSurface.blit(textSurf, textRect)
        pygame.display.update()
        time.sleep(0.04)
        numShufles-=1
        
        
    if evt==True:
            puzzle.sucessor(puzzle.StartNode)
            nxNode=puzzle.getNextNode()
            
            block=0
            for b in blocks:
                b['block']=str(nxNode[block])
                block+=1
                
                if b['block']=='0':
                    b['color']=BLACK
                else:
                    b['color']=GREEN         
                pygame.draw.rect(windowSurface, b['color'], b['rect'])
                textSurf = BASICFONT.render(b['block'], True,Text)
                textRect = textSurf.get_rect()
                textRect.center = b['rect'].left+50,b['rect'].top+50
                windowSurface.blit(textSurf, textRect)
            pygame.display.update()
            time.sleep(0.3)
            count=1
            
            while nxNode!=puzzle.GoalNode:
                #print(self.fronts)
                
                count+=1
                puzzle.sucessor(nxNode)
                nxNode=puzzle.getNextNode()
                block=0
                for b in blocks:
                    b['block']=str(nxNode[block])
                    block+=1
                    
                    if b['block']=='0':
                        b['color']=BLACK
                    else:
                        b['color']=GREEN         
                    pygame.draw.rect(windowSurface, b['color'], b['rect'])
                    textSurf = BASICFONT.render(b['block'], True,Text)
                    textRect = textSurf.get_rect()
                    textRect.center = b['rect'].left+50,b['rect'].top+50
                    windowSurface.blit(textSurf, textRect)
                pygame.display.update()
                time.sleep(0.03)
            break
                  
            
while True:
    # check for the QUIT event
    for event in pygame.event.get():
        if event.type == QUIT:
            pygame.quit()
            sys.exit()