Objects in a virtual space may be non-traversable such that traversal by characters of the virtual space through such objects is not permitted by the physics of the virtual space. Objects may be relocated during interactive gameplay. A navigation map of the virtual space is updated interactively, e.g. after an object has been relocated, by determining which regions are traversable or non-traversable, the boundaries of these regions, and which boundaries separate adjacent traversable regions. The updated navigation map may be queried on behalf of a non-player character in the virtual space, e.g. to determine where to go and/or how to get there.