Ok, so. Your moving players and CPU players. You store there location in a 2D grid. I assume you do this, so two players don't occupy the same grid square?
If so, then, each time a player goes to a new grid square, mark the old grid square unoccupied from the moment the player leaves, and at the same time, mark the new grid square occupied. Can't you do this from when you check each type object?
If so, then, each time a player goes to a new grid square, mark the old grid square unoccupied from the moment the player leaves, and at the same time, mark the new grid square occupied. Can't you do this from when you check each type object?