yeah I used a tilemap too (not an 'official' TileMap, just one I hacked up real fast), it isn't very expensive at all to do that. you can optimize it in a variety of ways.
for example... don't forget that technically your ghosts can "know" where pacman is at any time during gameplay, because the variables are all in the same scope. with this in mind, you do a quick check of where he is. so if my ghost hits an intersection, and pacman's position is higher than the ghost, I wouldn't bother looking DOWN for pacman.
my pacman clone was a 400x400 game, which used a 25x25 tilemap (each tile being 16x16). a grid of that size is cake when it comes to scanning around the tilemap for stuff - no performance issues at all for me