Why doesn't my function for scoring tiles in an array not work?

Question

I'm writing a small roguelike game for my university programming project. I wanted to try implementing a simple pathfinding mechanism, which would involve filling the tilemap with numbers going upwards from 0, the number being the distance to the player. This would allow the monsters to find the shortest path to the player. This is the algorithm I came up with:

void monster_vision(int player_x, int player_y, int score = 0)
{
    if (map[player_x][player_y] == '.')
    {
        map[player_x][player_y] = score;
    }
    else
        return;

    monster_vision(player_x - 1, player_y, score + 1);
    monster_vision(player_x + 1, player_y, score + 1);
    monster_vision(player_x, player_y - 1, score + 1);
    monster_vision(player_x, player_y + 1, score + 1);
}

as I said, this is just a single-file draft of the feature, the map is of type std::array<std::array<char, map_size>, map_size initially filled with # at the edges and dots inside

I expected the map to look something like this: for example, if the map's size is set to 5 and the function call is: monster_vision(2, 2)

#####
#212#
#101#
#212#
#####

what I get instead is:

#####
#218#
#307#
#456#
#####

from my understanding, some of the recursive calls must somehow overlap, but I thought the guard I put in place should be sufficient to prevent writing onto an already-scored cell.

[What is a debugger and how can it help me diagnose problems?](/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) and [Accessing an array out of bounds gives no error, why?](/questions/1239938/accessing-an-array-out-of-bounds-gives-no-error-why) — Jason, Mar 22 '23 at 11:21
I don't see any bounds-checking in your code. What happens if `player_x` or `player_y` goes out of bounds of your arrays? For example, in the call where you pass `player_x - 1` what happens if the result is `-1`? — Some programmer dude, Mar 22 '23 at 11:22
You are doing *depth-first search*. You should do *breadth-first search* instead. — MikeCAT, Mar 22 '23 at 11:25
You don't check for a shorter path. Your if statement should be `if (map[player_x][player_y] == '.' || map[player_x][player_y] > score)`. — B Remmelzwaal, Mar 22 '23 at 11:25
Consider that each recursive call will complete all of it's own recursive calls prior to returning. So you start in the middle, and set it to 0. Then it goes up, and sets it to 1. The it tries to go up again, and can't. Then down, can't. Then left and sets it to 2. In turn, this tries to go up, and cannot. So it goes down, which is available, and sets it to 3. Etc.. — ChrisMM, Mar 22 '23 at 11:27
@BRemmelzwaal thank you! Your solution fixed it! I'll also try researching BFS as MikeCat said, I completely forgot about it despite recently having finished a course on algorithms and data structures — aallfik11, Mar 22 '23 at 11:30
@aallfik11 You should _definitely_ use BFS here, as doing a DFS in this manner with the fix I provided will be slower for bigger maps :) — B Remmelzwaal, Mar 22 '23 at 11:32
The reason this doesn't work is because effectively you have a dfs-style search, but to compute shortest distance, you need bfs. — bitmask, Mar 22 '23 at 11:35
Also you are using `'.'` value as indication of "not visited" which is invalid and can collide with actual value of `score`! So in your code distance bigger then `46` is impossible. — Marek R, Mar 22 '23 at 11:56

score 1 · Answer 1 · edited Mar 22 '23 at 14:45

1

The problem is that your algorithm is recursive. Just imagine what it really does, it sets value 0 in your map (if .), then it calls monster_vision for next coordinate but for value 1. Now the magic happens. You are still inside the 2nd call to monster_vision, but now it calls monster_vision again (depth 2) for next position but value 2, etc.

Thus, the four calls to monster_vision that are below each other in your code are not called in a sequence. The sequence is iterative and is only broken when you hit the first non-. in all four "directions"... This is exactly what you observe.

An iterative algorithm sounds nice, but won't work.

Depending on your game logic you have to decide how you want to calculate distance/score, e.g. can monsters move diagonally?

I suggest a simple purely x/y movement and:

// map dimension is nx in first dimension and ny in second dimension here
void monster_vision(int player_x, int player_y)
{
    for (int i=0; i<nx; ++i) 
      for (int j=0; j<ny; ++j) {
         map[player_x][player_y] = std::abs(player_x-i) + std::abs(player_y-j);
}

However, as noted in the comments, in this particular case and many other cases it may be of no benefit to pre-compute the distances. Calculating them on-the-fly is possible and most likely preferable.

edited Mar 22 '23 at 14:45

bitmask

32,434
14
99
159

answered Mar 22 '23 at 13:02

Ralf Ulrich

1,575
9
25

That's a better approach if the movement pattern is defined as you say. The next step would be to realise that for such a movement pattern, pre-computing the entire map is unnecessary, because it will be much faster for each monster to compute its distance ad-hoc. – bitmask Mar 22 '23 at 13:16
@bitmask, of course you are right. The concept of a "map/array" here may be just wrong. – Ralf Ulrich Mar 22 '23 at 13:25
@RalfUlrich I know this isn't the scope of my question, but could you give me a little nudge in the right direction in terms of calculating the distances on the fly? My idea was to recalculate this "score map" if the player's position changes, but based on your response I assume there's a better way to do that – aallfik11 Mar 22 '23 at 13:57
2

@aallfik11 You do `std::abs(player_x-i) + std::abs(player_y-j)` (as here in this answer) whenever you want to query a distance instead of looking up the value in the map. – bitmask Mar 22 '23 at 14:41

score 1 · Answer 2 · answered Mar 22 '23 at 13:06

Here is an implementation using an std::deque to implement bfs:

  void computeDistances(Pos pos) {
    reset();
    std::deque<std::tuple<Pos, C>> q;
    q.emplace_back(pos,0);
    while (!q.empty()) {
      auto const [p, score] = q.front();
      q.pop_front();
      if (!(*this)[p]) {
        (*this)[p] = score;
        if (p[0] > 0) q.emplace_back(Pos{static_cast<C>(p[0]-1),p[1]}, score+1);
        if (p[1] > 0) q.emplace_back(Pos{p[0],static_cast<C>(p[1]-1)}, score+1);
        if (p[0] < N-1) q.emplace_back(Pos{static_cast<C>(p[0]+1),p[1]}, score+1);
        if (p[1] < N-1) q.emplace_back(Pos{p[0],static_cast<C>(p[1]+1)}, score+1);
      }
    }
    (*this)[pos] = 0;
  }

It relies on these helpers:

  using C = std::uint16_t;
  using Pos = std::array<C,2>;
  std::array<std::array<C, N>, N> map;

  C& operator[](Pos pos) {
    return map[pos[0]][pos[1]];
  }

  void reset() {
    std::fill(begin(map[0]), end(map[0]), 0);
    std::fill(begin(map), end(map), map[0]);
  }

Note that you don't need the border guards in the form of '#' characters because you know the size of the board. Instead a zero score is used to mark unvisited cells. Unfortunately this introduces a lot of branch conditions, which could be further improved.

Here is a complete demo.

Synopsis · Answer 3 · 2023-03-22T12:22:45.987

0

change

if (map[player_x][player_y] == '.')

to

if (map[player_x][player_y] == '.' || map[player_x][player_y]-char('0') > score)

to also set the new score in case of faster access and not only in case of first access.

edited Mar 22 '23 at 12:22

answered Mar 22 '23 at 12:03

Synopsis

190
10

1

Please add some explanation to your answer. – kiner_shah Mar 22 '23 at 12:04

Why doesn't my function for scoring tiles in an array not work?

3 Answers3