Most of the logic you ask for I wouldn't place in either tile or prototype. Send events to the map and let it be responsible to handle them. They are also your major tool in fighting depedencies. Some class enemy doesn't have to know what a tile is, just because it moves on them. It will not go and call oldTile->onLeave(me) and newTile->onEnter(me), but it will send event MoveEvent(me, fromPos, toPos).
This event will end up hitting the map which will grab the two prototypes and call their functions, passing the relevant tiles as parameters. If you are worried about too many dependencies, don't have everybody call functions on everybody else. Yes, this event system will be some form of "global", because it's the module everybody will use to communicate with everybody else.
Dependencies aren't created by what that article calls "hidden globals", but by design. Draw a bunch of boxes representing your class and modules and draw lines where you believe one must use the other. Notice how this design usually has nothing to do with implementation details of what is "global in disguise".
Another way (which can get very tedious very quick) is to forward everything over several layers, but when you end up with Game::movement calling World::movement calling Map::movement calling Tile::movement you will appreciate just sending an event and having everybody who cares (and registered for it) to handle it automatically. Downside is of course again in debugging. When your map ignores movement events, it's less straight forward to find out why.
Though seriously, for your first few games, focus on getting them done, not making them text book examples of squeaky clean programming. Trying to be holier than the pope (as we like to say over here) will keep you from making progress which often kills motivation and the project with it.
So then you're saying that using the small global in the example to store the list of tile prototypes is not bad in this case, then, right?