A method of providing a view of a three-dimensional map on a display of a client device, the method comprising performing, by the client device having a physical camera communicably coupled with the display: retrieving, from a map server, a set of map objects corresponding to a region of the 3D map; receiving, over a network, an origin position in the region of the 3D map, the origin position being specified by a host device; receiving, over the network, a first stream of virtual positions of a host virtual camera corresponding to the host device in the 3D map, wherein the first stream of virtual positions are relative to the origin position and are generated by physical movement of the host device; rendering and displaying a first series of images of the 3D map using the first stream of virtual positions of the host device; providing a user interface for a user to select a discovery mode that uses the physical camera; in response to a selection of the discovery mode via the user interface: capturing one or more first images of a physical environment within which the client device resides using the physical camera; determining an initial position of the physical camera in the physical environment using the one or more first images; determining a set of physical positions of a set of 3D objects of the 3D map relative to the initial position based on the origin position and the set of map obj ects; generating a second stream of virtual positions of a client virtual camera corresponding to the client device based on physical movement of the client device as measured using one or more second images from the physical camera; and rendering and displaying a second series of images of the 3D map using the second stream of virtual positions of the client virtual camera. retrieving, from a map server, a set of map objects corresponding to a region of the 3D map; receiving, over a network, an origin position in the region of the 3D map, the origin position being specified by a host device; receiving, over the network, a first stream of virtual positions of a host virtual camera corresponding to the host device in the 3D map, wherein the first stream of virtual positions are relative to the origin position and are generated by physical movement of the host device; rendering and displaying a first series of images of the 3D map using the first stream of virtual positions of the host device; providing a user interface for a user to select a discovery mode that uses the physical camera; in response to a selection of the discovery mode via the user interface: capturing one or more first images of a physical environment within which the client device resides using the physical camera; determining an initial position of the physical camera in the physical environment using the one or more first images; determining a set of physical positions of a set of 3D objects of the 3D map relative to the initial position based on the origin position and the set of map obj ects; generating a second stream of virtual positions of a client virtual camera corresponding to the client device based on physical movement of the client device as measured using one or more second images from the physical camera; and rendering and displaying a second series of images of the 3D map using the second stream of virtual positions of the client virtual camera. capturing one or more first images of a physical environment within which the client device resides using the physical camera; determining an initial position of the physical camera in the physical environment using the one or more first images; determining a set of physical positions of a set of 3D objects of the 3D map relative to the initial position based on the origin position and the set of map obj ects; generating a second stream of virtual positions of a client virtual camera corresponding to the client device based on physical movement of the client device as measured using one or more second images from the physical camera; and rendering and displaying a second series of images of the 3D map using the second stream of virtual positions of the client virtual camera.