Help implementing AI and Shadow in Maze Game

Hello, I need some help with the psuedocode for an AI in a Maze game.

I have all the functionality for the player and a basic ghosts movement around the maze, including moving floors, but my final assignment ask you to implement a couple new elements to the program but I'm not sure how I would go about doing these.

So first. The ghost must now ignore walls, if the ghost moves within five spaces of the player, it will begin moving toward the player, Distance is measured by "Manhatten Geometry."

Second. The current floor is now not shown to the player. The player can only see an area around his position up to a distance of 5 spaces. As the player moves, the revealed spaces remain that way, they aren't made blank again.

Here's what one of the floors looks like normally:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 ##############################
#      K                     #
#  ############## ### ###  # #
#      K    #   # #C# #K#  # #
# ######### # A # # # # #  # #
#      K    #   #          # #
# ############D#####D####### #
#                            #
#   C         G        C     #
#                            #
# ######D##############D#### #
#      #  C         #K#    # #
# #### ######## #   # #      #
# #K   #      # ### # # #### #
# # ## # #### #   # # #    # #
E # ## # #    ### # # #### # #
# #    # #K           D    # #
# #D#### ################### #
#                    K       #
############################## 


Then here is the current AI for the ghost:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void Ghost::move (Game & game)
{   Floor *     floor;
    int         r;
    bool        moved = false;

    floor = game.get_curr_floor();
    do
    {   r = rand() % 4;
        switch (r)
        {
        case 0:
            moved = floor->move_to_x_y (game, *this, 1, 0);
            break;
        case 1:
            moved = floor->move_to_x_y (game, *this, 0, -1);
            break;
        case 2:
            moved = floor->move_to_x_y(game, *this, -1, 0);
            break;
        case 3:
            moved = floor->move_to_x_y(game, *this, 0, 1);
            break;
        }
    }
    while (! moved);
}


It's pretty basic, the ghost just moves in four directions, at the same time as the player.

So any help regarding the above requirements would be greatly appreciated. I can't find any examples of an AI like this and have no idea how to implement the shadow effect on the maze.

Thanks for the help!
Quick mockup of fog of war (full of bad practices, just to illustrate the idea)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

size_t m_distance(std::pair<size_t, size_t> lhs, std::pair<size_t, size_t> rhs)
{
    using std::max;
    using std::min;
    size_t x_off = max(lhs.first,  rhs.first)  - min(lhs.first,  rhs.first);
    size_t y_off = max(lhs.second, rhs.second) - min(lhs.second, rhs.second);
    return max(x_off, y_off);
}

int main()
{
    std::vector<std::string> maze =
        {"##############################",
         "#      K                     #",
         "#  ############## ### ###  # #",
         "#      K    #   # #C# #K#  # #",
         "# ######### # A # # # # #  # #",
         "#      K    #   #          # #",
         "# ############D#####D####### #",
         "#                            #",
         "#   C         G        C     #",
         "#                            #",
         "# ######D##############D#### #",
         "#      #  C         #K#    # #",
         "# #### ######## #   # #      #",
         "# #K   #      # ### # # #### #",
         "# # ## # #### #   # # #    # #",
         "E # ## # #    ### # # #### # #",
         "# #    # #K           D    # #",
         "# #D#### ################### #",
         "#                    K       #",
         "##############################",};
    std::vector<std::vector<bool>> visible //variable to store our fog state
        { maze.size(), std::vector<bool>(maze[0].size(), false) };
    std::pair<size_t, size_t> coord = {6, 6};
    char c;
    do {
        system("cls");

        //clear fog
        for(size_t y = 0; y < maze.size(); ++y)
            for(size_t x = 0; x < maze[y].size(); ++x)
                if(m_distance(coord, {x, y}) < 5)
                    visible[y][x] = true;
        //Actual display
        for(size_t y = 0; y < maze.size(); ++y) {
            for(size_t x = 0; x < maze[y].size(); ++x)
                std::cout << (visible[y][x] ? maze[y][x] :'\xB0');
            std::cout << '\n';
        }
        //Quick movement mockup
        std::cin >> c;
        switch(c) {
          case '8': --coord.second; break;
          case '2': ++coord.second; break;
          case '4': --coord.first;  break;
          case '6': ++coord.first;  break;
        }
    } while (c != '0');
}
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░ ##############░░░░░░░░░░░░░
░░     K    #   #░░░░░░░░░░░░░
░░######### # A #░░░░░░░░░░░░░
░░     K    #   #░░░░░░░░░░░░░
░░############D##░░░░░░░░░░░░░
░░               ░░░░░░░░░░░░░
░░  C         G  ░░░░░░░░░░░░░
░░               ░░         ░░
░░######D########░░####D####░░
░░░░░░░░  C         #K#    #░░
░░░░░░░░####### #   # #     ░░
░░░░░░ #      # ### # # ####░░
░░░░░░ # #### #   # # #    #░░
░░░░░░ # #    ### # # #### #░░
░░░░░░ # #K           D    #░░
░░░░░░## ###################░░
░░░░░░               K      ░░
░░░░░░######################░░


For ghosts: for each ghost check its distance to player. If he is at or closer than the distance of 5, then move ghost towards it.


EDIT: I misread your second problem. In this case have an array of booleans same size as your map. initially it filled with false. When you move, set all values within certain distance to true. When drawing, check corresponding bool, and draw either tile or fog depending on it.

EDIT2: replaced code with fixed version
Last edited on
The ghost must now ignore walls

Based on the code we've been working on, Floor::legal_move() would need to change so that a ghost can move through a wall, but a player can't. Keep in mind the old problem of the current move function replacing the current tile with a space. i.e. with the current code, if a ghost moves through a wall, it will leave a hole in the wall.

The best way to fix this is to have Character remember the tile it was on. When a character moves, it puts back the value of the tile it was on and saves the value of the tile it is moving to. This belongs in Characters as it should work for both Player and Ghost. Doors and cherries might require special consideration. If you unlock a door, does the door remain unloocks (blank), or does it lock again (put the D back)? For cherries, you don't want to put them back.

The current floor is now not shown to the player

This is pretty easy. As Miinipaa suggested, each floor will need a 2D bool array (corresponding to the tiles array) to indicate which tiles a player has seen. Each time the player moves, you update the appropriate flags indicating the player has seen more tiles. When displaying the maze, you only display the tiles which have been marked as having been seen. Don't forget when you change floors to mark the tiles around the ladder exit as having been seen.
Last edited on
Topic archived. No new replies allowed.