CODEWITHSUNDEEP
javaalgorithm
ComputerLocus
ComputerLocus

Reputation: 3618

How to make a AI system that chooses fastest way and navigates through walls to a certain grid spot

Basically I'm trying to improve on the Ghosts in a Pacman game I'm making. In the orginal pacman when a Ghost is eaten when Pacman has picked up the Power the Ghosts eyes would navigate back to the home area and then spawn the ghost back in. I would like to do this to. It would also help me with implementing a Ghost AI to make them move smarter then just random.

So basically those eyes would have to navigate through this:

pacman area

And the board is being drawn from the below 2D array:

  //0's = Walls or location not allowed to go
  //1's = Dot Spot
  //2's = Clear Path nothing on it but safe to move
  //3's = Power Dot
  //-1's = only ghosts can go through
  //5= Top entry spot
  //6= bottom entry point
  //7 = Cherry
  //(Spots = row - 1 same with columns = - 1. First # is row. Second is col
  public int board[][] =
  {{2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}, //1
    {2, 0, 3, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 3, 0, 2}, //2
    {2, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 2}, //3
    {2,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,2}, //4
    {2,0,1,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,2}, //5
    {2,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,2}, //6
    {2,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,2}, //7
    {2,2,2,2,0,1,0,1,1,1,1,1,1,1,0,1,0,2,2,2,2}, //8
    {0,0,0,0,0,1,0,1,0,0,-1,0,0,1,0,1,0,0,0,0,0}, //9
    {5,2,2,2,2,1,1,1,0,2,2,2,0, 1 ,1,1,2,2,2,2,6}, //10 - cherry
    {0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0}, //11
    {2,2,2,2,0,1,0,1,1,1,2,1,1,1,0,1,0,2,2,2,2}, //12
    {2,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,2}, //13
    {2,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,2}, //14 - pacman on this row
    {2,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,1,0,2}, //15
    {2,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,2}, //16 
    {2,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,2}, //17
    {2,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,2}, //18
    {2,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,2}, //19
    {2,0,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,0,2}, //20
    {2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2}}; //21

So my question is how should I go about making the eyes go to the centre home spot in the fastest way without going through walls?

Upvotes: 1

Views: 1156

Answers (2)

Rafe
Rafe

Reputation: 5295

Just use a precomputed inkblot. The "home" squares are labelled zero. Then, all unassigned neighbour squares of a square labelled n are assigned label n +1. Now all your "dead" ghosts have to do is move to a neighbouring square with a lower label. Eventually they will get home having taken the shortest path. Easy!

Upvotes: 3

Tudor
Tudor

Reputation: 62439

You can look into Lee's algorithm for shortest path inside a matrix with obstacles.

Upvotes: 2

Related Questions