Java – Pacman role AI suggests the best next direction

First, this is Pacman's AI, not the ghost

I'm writing an Android dynamic wallpaper to play Pacman around your icon Although it supports user suggestions through screen touch, most games will be played by AI I have 99% finished all the programming of the game, but Pacman's own AI is still very weak I am looking for help to develop a good AI to determine Pacman's next travel direction

My initial plan was this:

>Initializes a score counter for each direction with a value of zero. > Start at the current location and use BFS to traverse outward in four possible initial directions by adding them to the queue. > Pop up an element from the queue, ensure that it has not been "seen", ensure that it is a valid circuit board position, and add it to the corresponding initial direction to score the value of the current cell according to the following contents:

>There is a point: add 10 > power on: add 50 > fruit: add fruit value (depending on the level) > ghost travels to Pacman: subtract 200 > a ghost leaves Pacman: do nothing > ghost moves vertically: subtract 50 > multiply the value of the cell by the percentage based on the number of steps in the cell. The more steps from the initial direction, the closer the value of the cell is to zero

And arrange three possible directions from the current cell. > When the queue is empty, find the highest score in each of the four possible initial directions and select the score

This sounds good to me on paper, but the ghost surrounds Pacman very quickly. He twitches back and forth in the same two or three cells until a man reaches him Adjusting the value of ghost presence does not help Before the end of the game, my nearest BFS can reach at least level 2 or 3

I am looking for code, ideas and / or resource links to develop the appropriate Ai - preferably the first two I want to release this in the market sometime this weekend, so I'm in a bit of a hurry Any help is greatly appreciated

For reference only, this is in GameDev Stackexchange manual cross Publishing

Solution

If Pacman is stuck in one position and starts twitching back and forth, it shows that the scores of different actions open to him are very similar after you run your indicator Then a small position change of the ghost will cause the best movement to flip back and forth You may need to consider adding some hysteresis to prevent this from happening

Setting: select random movement and record it as a score of 0

For each step:

>Run the scoring function on the available mobile. > If the highest score is x% greater than the recorded score, the recorded score is overwritten and moves with it. > Apply for a move

This will cause Pacman not to choose the "best" action of each step, but it seems that greedy local search is not the best This will make Pacman more stable and stop convulsions