My image-loading code has a rudimentary scrollable viewport over a frame buffer, so I started a Pacman with a 3x3 cell size (so it could show a bit of detail), but stopped because the image data was so big it was making the pattern editor hang.
I wasn’t going to bother with an optimal pursuit algorithm; I was planning to have the NPCs move until they hit a wall, then turn whichever direction was closer to the current location of the Pacman.
If you’re using a queue, the maximum size would be a bounded multiple of the number of possible positions so you could still allocate a fixed-size array…