TSUKAHARA TSUBASA (US)
SONY CORP AMERICA (US)
US20210248826A1 | 2021-08-12 | |||
US20090197686A1 | 2009-08-06 | |||
US20210283497A1 | 2021-09-16 | |||
US17488245A | ||||
US17488247A | ||||
US17488248A | ||||
US17488249A | ||||
US17488250A | 1950-07-20 | |||
US17488251A | ||||
US17488253A |
Claims We claim: 1. A method for predefining a virtual staircase connecting real platforms in an XR space; the method comprising: accessing a previously generated spatial mapping mesh (SMM) in which the XR space is defined, the SMM including physical elements present in that space; compiling a record from the SMM of all available surfaces of the physical elements in the XR space, with corresponding surface positions and dimensions; identifying, from the record, available platforms provided by the physical elements and available open spaces between the physical elements; selecting, from the available platforms, a first platform at a first level and a second platform at a second level, wherein the first level is higher than the second level by a separation greater than a predefined threshold; selecting a staircase start location at a first edge of the first platform, based in part on predetermined criteria; and stacking virtual blocks in contact linearly to form a current virtual staircase, such that a first virtual block in the staircase contacts and extends outwards from the first platform, and a last virtual block in the staircase contacts the second platform at a staircase end location; and performing a collision analysis for the current virtual staircase; wherein if the staircase end location satisfies the predetermined criteria, and if no collisions are found by the collision analysis, the current virtual staircase connecting the first and second platforms is displayed in subsequent user interactions with the XR space. 2. The method of claim 1, wherein the predetermined criteria for a location comprise requiring that, at that location: a volume of available open space is greater than a predetermined volume; and an available open entry path from, or exit path to, other available open spaces in the XR space exists. 3. The method of claim 2, wherein the predetermined volume is determined in part by dimensions of a user-controlled character in a video game designed to be played in the XR space. 4. The method of claim 2, wherein the predetermined volume is determined in part by flexibility or dexterity characteristics of a user-controlled character in a video game designed to be played in the XR space. 5. The method of claim 2, wherein the existence of an available open entry path or exit path is determined by performing an endpoint collision analysis at that location. 6. The method of claim 5, wherein performing an endpoint collision analysis at that location comprises: generating a virtual collider block shaped and sized according to dimensions of a user-controlled character in a video game designed to be played in the XR space; scanning the virtual collider block outward, relative to a corresponding surface edge, from that location; and recording a distance from that location to a barrier location at which the virtual collider block collides with an adjacent physical element in the XR space as determining the available open space adjacent that location. 7. The method of claim 1, further comprising, if either the staircase end location does not satisfy the predetermined criteria or a collision is found by the collision analysis: iteratively twisting the current virtual staircase such that at each twist iteration the current virtual staircase is updated, with the first virtual block remaining in place relative to the first platform and the last virtual block contacting the second platform at an updated staircase end location; wherein if the updated staircase end location satisfies the predetermined criteria, and if no collisions are found by a collision analysis for the updated current virtual staircase, the updated current virtual staircase connecting the first and second platforms is displayed in subsequent user interactions with the XR space. 8. The method of claim 7, further comprising, if none of the twist iterations provides an updated staircase end location that satisfies the predetermined criteria and an updated current virtual staircase that encounters no collisions during the collision analysis: iteratively shifting the current virtual staircase such that at each shift iteration, the current virtual staircase is updated, with the first virtual block shifted along the first edge of the first platform to a shifted staircase start location that satisfies the predetermined criteria, causing the last virtual block to contact the second platform at a shifted staircase end location; wherein if one of the shift iterations provides a shifted staircase end location that satisfies the predetermined criteria, and if no collisions are found by a collision analysis for the updated current virtual staircase, the updated current virtual staircase connecting the first and second platforms is displayed in subsequent user interactions with the XR space. 9. The method of claim 1, wherein the predefined threshold is determined at least in part by a characteristic of a user-controlled character in a video game designed to be played in the XR space. 10. The method of claim 1, wherein the SMM was generated by a device worn, carried, or deployed by a user of a video game designed to be played in an XR environment. 11. A system for predefining a virtual staircase connecting real platforms in an XR space; the system comprising: one or more processors; and logic encoded in one or more non-transitory media for execution by the one or more processors and when executed operable to: access a previously generated spatial mapping mesh (SMM) in which the XR space is defined, the SMM including physical elements present in that space; compile a record from the SMM of available surfaces of the physical elements in the XR space, with corresponding surface dimensions; identify, from the record, available platforms provided by the physical elements and available open spaces between the physical elements; select, from the available platforms, a first platform at a first level and a second platform at a second level, wherein the first level is higher than the second level by a separation greater than a predefined threshold; select a staircase start location at a first edge of the first platform, based in part on predetermined criteria; stack virtual blocks in contact linearly to form a current virtual staircase, such that a first virtual block in the staircase contacts and extends outwards from the first platform, and a last virtual block in the staircase contacts the second platform at a staircase end location; and perform a collision analysis for the virtual staircase; wherein if the staircase end location satisfies the predetermined criteria, and if no collisions are found by the collision analysis, the current virtual staircase connecting the first and second platforms is displayed in subsequent user interactions with the XR space. 12. The system of claim 11, wherein the predetermined criteria for a location comprise requiring that, at that location: a volume of available open space is greater than a predetermined volume; and an available open entry path from, or exit path to, other available open spaces in the XR space exists. 13. The system of claim 12, wherein the predetermined volume is determined in part by dimensions of a user-controlled character in a video game designed to be played in the XR space. 14. The system of claim 12, wherein the predetermined volume is determined in part by flexibility or dexterity characteristics of a user-controlled character in a video game designed to be played in the XR space. 15. The system of claim 12, wherein the existence of an open entry path or exit path is determined by performing an endpoint collision analysis at that location. 16. The system of claim 15, wherein performing an endpoint collision analysis at that location comprises: generating a virtual collider block shaped and sized according to size and shape of a user-controlled character in a video game designed to be played in the XR space; scanning the virtual collider block outward, relative to a corresponding surface edge, from that location; and recording a distance from that location to a barrier location at which the virtual collider block collides with an adjacent physical element in the XR space as determining the available open space adjacent that location. 17. The system of claim 11, the logic further operable to, if either the potential staircase end location does not satisfy the predetermined criteria or a collision is found by the collision analysis: iteratively twist the current virtual staircase such that such that at each twist iteration the current virtual staircase is updated, with the first virtual block remaining in place relative to the first platform and the last virtual block contacting the second platform at an updated staircase end location; wherein if the updated staircase end location satisfies the predetermined criteria, and if no collisions are found by a collision analysis for the updated current virtual staircase, the updated current virtual staircase connecting the first and second platforms is displayed in subsequent user interactions with the XR space. 18. The system of claim 17, further comprising, if none of the twist iterations provides an updated staircase end location that satisfies the predetermined criteria and an updated current virtual staircase that encounters no collisions during the collision analysis: iteratively shifting the current virtual staircase such that at each shift iteration, the current virtual staircase is updated, with the first virtual block shifted along the first edge of the first platform to a shifted staircase start location that satisfies the predetermined criteria, causing the last virtual block to contact the second platform at a shifted staircase end location; wherein if one of the shift iterations provides a shifted staircase end location that satisfies the predetermined criteria, and if no collisions are found by a collision analysis for the updated current virtual staircase, the updated current virtual staircase connecting the first and second platforms is displayed in subsequent user interactions with the XR space. 19. The system of claim 18, wherein the predefined threshold is determined at least in part by a characteristic of a user-controlled character in a video game designed to be played in the XR space. 20. The system of claim 11, wherein the SMM was generated by a device worn, carried, or deployed by a user of a video game designed to be played in an XR environment. |
[46] In some simple embodiments involving a single virtual character, activity categories may include, for example, one or more of sitting, jumping up and down, climbing, kneeling, leaning, lying down, putting a virtual object on a surface or lifting one off. The type of surface and its orientation are obviously relevant, as some activities would naturally suit a low horizontal surface: kneeling would suit a floor, or a rug, for example, others like lying down might suit a sofa or a bed, while yet others like leaning might suit a wall or a vertical side of a tall bookcase.
[47] Another factor that may be taken into account in assigning an activity zone to an activity category is the size of the surface or surfaces in the vicinity of the activity zone, the size being determined by surface dimensions which are a part of the SMM record. Yet another factor may be the size of the activity zone itself, basically the dimensions of the open space determined by the collision analysis relative to the dimensions of one or more virtual characters that might be positioned there to carry out that type of activity For example, the space needed for a large character to run around the table would be greater than the space needed for that same character to sit down at that table in a virtual chair, which in turn might be greater than the space needed for a smaller character to sit down at that same table in a correspondingly smaller virtual chair.
[48] Method 300 is essentially complete after step 350 has been carried out, allowing a character in an XR game (or other application) subsequently set in the XR space addressed by the method to participate in an activity appropriate to their location, in a manner that is believable to the user.
[49] In some embodiments, a plurality of activity zones in close proximity to each other may be assigned to a group activity category involving two or more non-player character (NPCs) interacting with each other as well as with real surfaces in a video game designed to be played in the XR space. The group activity category may be one of: conversation, playing a multi-player card game, throwing and catching a ball, and sharing a platter of food. [50] In some other embodiments, the group activity category may involve interaction with more than one available nearby surface. For example, one character may pick up virtual darts from a surface of a real table, and throw them at a virtual dartboard on a real wall, while another player near the wall pulls the darts out and returns them to the table. [51] Returning to Figure 4, the left hand part shows a part of an XR space where method 300 has been used to determine four activity zones 420A-420D, shown as grey circular blobs, each located at or near one of the four side edges of tabletop 410. Note that these blobs are not actually shown to the user during game play, but are useful aids to the game designer during game development. As mentioned above, as these zones are clustered around a single surface that is recognized to be a tabletop, they may be assigned together to one or more group activity categories, like playing a multi-player card game, or having a group discussion over a meal. The right hand part of the figure shows a situation where three of the four sides of another tabletop 440 are effectively blocked by chairs, so the only area which could be defined as an activity zone is area 450, again shown as a grey circular blob. [52] It should be noted that neither a representative graphical indication of position (like the grey blobs shown in Figure 4) nor virtual boundaries of the corresponding activity zone itself will actually be made visible to the user during XR game play. [53] Figures 5-7 relate to “reachable item placement” embodiments. [54] Figure 5 illustrates how some of these embodiments may allow for XR spaces, present in real environments such as simple living rooms containing typical items of furniture, may be populated with virtual items so that a virtual character may subsequently be able to “discover” them 2 , and find a path to reach them from whichever “spawn” position the player finds themselves at, as a starting point. [55] Specifically, the example illustrated by Figure 5 is an XR space 500 in a room filled with physical elements (crudely represented here as cuboids for simplicity) such as 510 and 511. Spatial mapping mesh 530 should be understood as covering all exposed surfaces of the elements in the XR space, although, for clarity, the mesh polygons are only indicated by hatching at two representative surface, the back wall and the floor. The virtual item 540 to be placed in advance of the game being played is shown as being cylindrically shaped, with an aspect ratio that suggests a coin, but of course this is just one example; Position 550A is one possible position in which item 503 could reasonably be placed, to potentially be able to be accessed by virtual character 560 from spawn position 560. Position 550B, however, although in an unoccupied space between real physical elements 510 and 511 might not be a reasonable position to be placed if it is sufficiently far back (relative to front surfaces of 510 and 511 as viewed by player 560) that player 560 could not be expected to reach it. [56] Figure 6 is a flowchart of method 600 according to some reachable item embodiments of the present invention, for the type of scenarios shown in Figure 5. [57] At step 610, a Spatial Mapping Mesh (SMM), previously generated using at least one of the devices discussed above is obtained, containing information on locations of myriad tiny portions of each exposed surface in the environment probed by the device. The SMM is intrinsically limited to exposed surfaces, in the sense that only surfaces that are detectable by the technology used by the mapping device in question can be included. [58] At step 620, a record is complied, using information in the SMM, of all open spaces between those surfaces of physically real elements in the XR space, with corresponding positions and dimensions. [59] At step 630, a spawn position that would be suitable for the virtual character in the subsequent game is selected from the record of open spaces (where suitability is based on the character’s size, and possibly skill and ability levels); and some primary positions other than the spawn position are selected from that same record, at random other than excluding the spawn position. The order is immaterial – in some embodiments the primary positions might be chosen before the spawn position is. [60] At step 640, a filtering operation is carried out on the open spaces corresponding to the selected primary positions to yield a subset of positions potentially suited to a placement location for the virtual item. This typically comprises applying a size threshold to exclude open spaces too small to comfortably accommodate the virtual item, although other constraints may be added to keep the number of positions in the subset to a manageable number or for other reasons discussed below. [61] At step 650, a collision analysis is carried out at each position in the subset of positions, allowing a score to be assigned based at least in part on accessibility to that position for the virtual character, beginning from the spawn position. Another factor that may affect the score in some embodiments is excessive distance from the spawn position. In some embodiments, the analysis comprises, for each position in the subset, generating a virtual collider block shaped and sized according to size and shape of the first virtual item, moving a virtual collider block along all possible paths from the spawn position to that position and recording all collisions with real surfaces along those paths [62] At step 660, if one position in the subset has a higher score than any other, the virtual item is placed at that position, while if there are two or more positions that tie for the highest score, the virtual item is placed at one of those two or more positions, randomly or on the basis of some other criterion. One possible criterion that may be used is one based on the desired level of difficulty for the game – a position much higher or much lower than eye level for the character may be considered more difficult than the others, for example. [63] Method 600 is essentially complete after step 660 has been carried out, allowing a character in an XR game (or other application) subsequently set in the XR space addressed by the method to reach a virtual item placed in the position defined by the method, in a manner that is believable to the user. There are many games that challenge a character, in particular a virtual character, to “search for” a virtual item and take it. Doing this in an XR environment, where the item is positioned in a space between real physical items seen by the user may be particularly satisfying to the user. [64] In some instances of these “collector” games, there may be a plurality of virtual items for the character to find and pick up, with the goal being to collect as many as possible, maybe in a given time, and/or in competition with other characters. For these games, a variation of method 600 is needed, such as method 700 illustrated by Figure 7. [65] Steps 710, 720, 730, 740, 750, and 760 of method 700 correspond almost exactly to steps 610, 620, 630, 640, 650 and 660 of method 600, but applied to a situation where there are two virtual items to be placed rather then one. At step 760, for eample, just one of the two items is placed at the position that has been determined by the collision analysis of step 750 to have the highest score (or at one of two or more positions which tie for that highest score) as described above for the single virtual item embodiments of Figure 6. [66] At step 770, the subset of positions for which a score has been determined at step 750 (in the same way described above for step 630 of method 600) is then revised to remove the position at which the first virtual item was placed. Then at step 780, the second virtual item can be placed at whichever position in the revised subset has been determined by the collision analysis of step 750 to have the highest score (or at one of two or more positions which tie for that highest score) compared to all other positions in that revised subset. [67] In some embodiments the revision step 770 may exclude other positions as well as the position at which the first virtual item was placed. For example, it may exclude other positions that are closer to the first position than a predetermined distance, so that the challenge to the virtual character is kept within a desired difficulty range. [68] For simplicity, in method 700 it is assumed that the two virtual items are of the same size though it may readily be appreciated that the details of filtering step 740 may include different filters for embodiments in which the two items are of different sizes. [69] It should be apparent that additional steps following the pattern of steps 770 and 780 may be added as needed for embodiments requiring successively greater numbers of placement locations to be found for correspondingly greater numbers of virtual items. [70] In some multi-item embodiments, more complex strategies may be involved in choosing placement locations beyond the primary criterion of “highest score”. For example, one embodiment might deliberately choose a mixture of “easy to access” locations and “hard to access” locations, and adjust the ratio of easy to hard depending on a desired difficulty level for the game for a given user, or a particular occasion. In these cases, at least some locations that are not the highest scoring may be chosen for placement positions. [71] In some cases, it may be desirable to try to present users in different XR spaces with game experiences that are of roughly equal difficulty. One way of doing this might be to adjust the number of virtual items placed according to the size of the XR space, or to the density of real surfaces present. Another strategy might be to avoid placing virtual items so close together that finding one would almost certainly mean finding the others, by imposing a “minimum separation” threshold between placing the nth virtual item and the (n+1)th virtual item. Many other variations may be envisaged by those of ordinary skill in the art of game design. [72] Figures 8-11 relate to platform connecting embodiments. [73] On the left hand side of Figure 8 is an example of an XR environment in which a virtual character would benefit by having access to a virtual staircase, positioned according to platform connecting embodiments. Only some parts of a Spatial Mapping Mesh 830 are shown by hatching on surfaces of the right hand wall and the back wall of the XR space 800, but as in the cases discussed above of space 500 in Figure 5, surfaces of all physical elements within space 800 would actually be covered by that mesh. Consider the situation where virtual character 840 might want to reach the top surface 860 of a physical object in the room, shown as a simple cuboid here, for simplicity. If the character were standing on the floor right next to the object, the height of surface 860 above floor level would be too great for the character to reach it by jumping or climbing. Similarly, if character 840 were able to reach a top surface 850 of another, nearby object in the room (the horizontal separation is exaggerated for clarity in the figure), the vertical separation between 850 and 860 might still be too great for any efforts on the part of character 840 to traverse, left to their own devices. Now see the right hand side of Figure 8 where the same XR space is shown, but with the addition of a virtual staircase 810, made up of N virtual blocks, 820:1 through 820:N, spanning the space between 850 and 860, making it easy for character 840 to reach either surface from the other. [74] Another possibility (not shown) would be to add another virtual staircase between level 860 and floor level. [75] Figure 9 shows two screenshots taken from an actual video game under development, where a virtual character is making their way between platforms at different levels by using virtual staircases, positioned 3-dimentionally in XR space according to embodiments of the method described below with reference to Figure 10. On the left hand side, XR space 910 (possibly a hobby room or workshop) shows virtual character 900 who has just run down virtual staircase 914 from a real tabletop surface 916 to the top surface 916 of a real stack of drawers. On the right hand side of the figure, the same character is shown in another XR space 920 (possibly an office or living room), running along the top surface 926 of the back of a sofa, after having run up virtual staircase 924 from the top surface 928 of a desk. Virtual staircases 914 and 924 are positioned in the respective XR spaces according to embodiments [76] Fig 10 is a flowchart of method 1000 according to some platform connecting embodiments of the present invention, relevant to scenarios such as those illustrated in Figures 8 and 9. [77] At step 1010, a Spatial Mapping Mesh (SMM), previously generated using one of the devices discussed above is obtained, containing information on locations of myriad tiny portions of each exposed surface in the environment probed by the device. The SMM is intrinsically limited to exposed surfaces, in the sense that only surfaces that are detectable by the technology used by the mapping device in question can be included. [78] At step 1020, a record is complied, using information in the SMM, of surfaces of real physical elements in the XR space, with corresponding positions and dimensions. [79] At step 1030, available platforms and surrounding open spaces are identified from the record, and first and second platforms that are good candidates to be connected are selected. The selection includes selecting a first platform at a first level and a second platform at a second level, wherein the first level is higher than the second level by a separation greater than a predefined threshold. This avoids spending resources on creating staircases that a virtual character in an XR game likely to be played in the XR space would not really need, as they could step or jump from one to the other without the extra help. In some embodiments, the predefined threshold is determined by at least one known characteristic of the virtual character, such as their height and jumping ability. [80] In some embodiments, the selection may include filtering out platforms too small or too uneven to be worth considering, platforms that would be indirectly accessible to the character as they are close enough to others that are directly reachable, and so on. [81] At step 1040, a staircase start location is selected at one edge of the first platform, closest to the nearest edge of the second platform. This will typically be at a central point between adj acent corners of the platform, but the process involves choosing a location subject to predetermined criteria, aimed at ensuring there is adequate access to that location for a character that may need it. In some embodiments, the criteria amount to requiring that, at that location: a volume of available open space must be greater than a predetermined volume; and that an available open entry path from, or exit path to, other available open spaces in the XR space exists. Typically, the predetermined volume is determined in part by dimensions of a user-controlled character in a video game designed to be played in the XR space. In some embodiments, the predetermined volume may be determined in part by flexibility or dexterity characteristics of that character.
[82] In some embodiments, the existence of an available open entry path or exit path is determined by performing a collision analysis at that location. Performing a collision analysis at that location typically comprises: generating a virtual collider block shaped and sized according to dimensions of a user-controlled character in a video game designed to be played in the XR space; scanning the virtual collider block outward, relative to a corresponding surface edge, from that location; and recording a distance from that location to a barrier location at which the virtual collider block collides with an adjacent physical element in the XR space. The recorded distance can be taken as determining the available open space adjacent that representative position. If it is larger than a predetermined threshold for the character anticipated as needing to use that space, an open entry or exit path can therefore be assumed.
[83] At step 1050, virtual blocks are stacked in a linear staircase formation, beginning at the top with a first block positioned at the staircase start location, continuing with a second block offset along outwards along a direction perpendicular to the edge of the first platform and so on, until a last virtual block contacts the second platform at a staircase end location. This creates a current version of a virtual staircase.
[84] At step 1060, a collision analysis is carried out for the current virtual staircase, to check for the presence of any intervening real surfaces overlapping or too close to the staircase. The analysis would preferably take a dimension (typically the height) of a character that might use the staircase in a subsequent XR game into account, to make sure there is adequate free space to allow that use.
[85] At step 1070, if no collisions are detected along the extent of the virtual staircase, and if the staircase end location satisfies the same predetermined criteria used at step 1040 for the staircase start location, the method proceeds to step 1080 at which the current virtual staircase is accepted, meaning that the connected group of virtual blocks will be displayed at its current positioning and orientation, connecting the first and second platforms, in subsequent user interactions with the XR space.
[86] In some other embodiments, not shown, the predetermined criteria may be different at the two ends of the staircase.
[87] In cases where, at step 1070, it is found that there are collisions or that the staircase end location criteria are not satisfied (or both), the method proceeds to step 1090 rather than 1080, and a twist or spin in applied to the connected virtual blocks, updating the staircase orientation and the positioning of the bottom end of the staircase, before step 1060 is performed for a second time. If it is then determined at the next path through step 1070 that the twisted orientation is free of collisions and has produced an updated potential staircase end location that satisfies the predetermined criteria, the method proceeds to 1070, and the current (updated) staircase is accepted, as discussed above. If it has not, further iterations are performed, each with a corresponding new twist.
[88] Fig 11 is a flowchart of method 1100 according to some other platform connecting embodiments of the present invention, relevant to the same type of scenarios illustrated in Figures 8 and 9.
[89] Steps 1110 through 1180 correspond exactly to steps 1010 through 1070 of method 10. The difference occurs at step 1190, which is only reached if it is determined at step 1170 that either a collision occurs or the criteria applied to the staircase end location are not met (or both). In that case, rather than twisting the staircase blocks, a straight linear orientation is maintained but the staircase itself is shifted to update the staircase start location to a new location on an edge of the first platform (which in turn would update the staircase end location). The shift may be a small one, to a different location along the same platform edge, or a more extensive one to a location at a different edge of the same platform. The predetermined criteria used at step 1140 (corresponding to 1040 in method 1000 discussed above) would of course have to be satisfied in making the shift. Then steps 1160 and 1170 are performed for a second time. If the shifted orientation has produced a collision free staircase and an updated staircase end location that satisfies the predetermined criteria, the method proceeds to 1180, and the current (updated) staircase is accepted, as discussed above with respect to 1080 in method 1000. If a collision is detected or if the end location of the shifted staircase does not satisfy the criteria, further iterations are performed, each with a corresponding new shift. [90] Various combinations of methods 1000 and 1100 may be envisaged, such as, for example, one type where a fixed number of twisted orientations are attempted before, if necessary, the same number of shifted orientations are. In some embodiments, the fixed number may be one, meaning that each twisted orientation may be followed by a shifted and back again, for as many iterations as necessary to find an updated staircase end location that satisfies the predetermined criteria so that the corresponding virtual staircase can be accepted. [91] In yet other embodiments, instead of settling on the first virtual staircase whose end location is found to satisfy the predetermined criteria, the method may continue in the hope of finding two or more virtual staircases that satisfy the predetermined criteria. In these cases, a choice will be made of one of the two or more virtual staircases on the basis of some additional criterion, such as whichever one has a start location with the largest volume of open space around it. [92] It should be noted that although much of the above discussion of platform connecting embodiments has concerned building virtual staircases from the top down, with the first level being above the second level, of course the same basic ideas could be applied in the opposite sense, building virtual staircases from a lower level to an upper one. [93] It should also be noted that while this disclosure focuses on cases where the two platforms are at different vertical levels, the inventive ideas discussed herein could readily be adapted and extended to cover situations where a gap between two platforms is too large for the character to step or jump across, so that a substantially horizontal bridge rather than a staircase could be a good solution. Essentially the same considerations of choosing suitable start and end locations with adequate access, avoiding collisions with nearby surfaces etc. would apply to such bridge embodiments, requiring essentially corresponding method steps to those discussed for the staircase embodiments. [94] Embodiments of the present invention provide many benefits. In general terms, methods described above allow a user of an XR environment, which may be a room in the user’s home or business premises in which the methods were applied prior to the user playing the XR game (or using another XR application of interest) to experience a greater sense of immersion in that XR environment than would otherwise be achieved. [95] In those instances where the methods are applied to find and categorize activity zones, virtual characters in the XR environment can be presented carrying out believable actions with respect to real elements present in the environment, even though the developer of the XR game (or other XR application) would have had no knowledge at all of what (or where exactly) real elements would actually be present in that particular user’s surroundings. [96] In those instances where the methods are applied to find placement positions from which virtual items may be collected by a virtual character, that character – or rather the real user – may find the task less frustrating and more satisfying and engaging than if the positions were randomly distributed through XR space without regard to the real elements actually present. [97] In those instances where the methods are applied to find start and end locations for virtual staircases, a virtual character who would otherwise be unable to traverse spaces between a pair of real platforms at different levels in an XR space is enabled to do in a believable, relatively natural way, again increasing user engagement and immersion in the XR environment. [98] The methods disclosed are computationally efficient, in taking pains to reduce the volumes of data being processed to focus on the most relevant regions of space within the XR space as a whole. In many activity zone embodiments, for example, the collision analysis may only be carried out in the immediate surroundings of relatively large surfaces, most likely to be of interest, rather than addressing every single open space identified in the SMM. For some reachable item embodiments, the filtering step before the collision analysis may exclude open spaces too large or too small to be good hiding places, and in some platform connecting embodiments, a starting position too close to an alternative existing route between platforms may be eliminated during the initial selection step of the staircase predefining method. [99] As noted earlier, the present invention is not limited to games alone. Relatively straightforward examples of non-gaming applications include navigation, shopping, and apps involving chatting with virtual characters, but other more speculative examples may be envisaged, such as (1) determining how connectable surfaces are to each other and the floor to assess how cluttered a room is and/or how navigable it is to a child of a particular height, a person with disabilities; (2) more directly helping users with disabilities navigate a particular space; and (3) trajectory planning and control for drones. [100] Although the description has been described with respect to particular embodiments thereof, these particular embodiments are merely illustrative, and not restrictive. [101] Any suitable programming language can be used to implement the routines of particular embodiments including C, C++, Java, assembly language, etc. Different programming techniques can be employed such as procedural or object oriented. The routines can execute on a single processing device or multiple processors. Although the steps, operations, or computations may be presented in a specific order, this order may be changed in different particular embodiments. In some particular embodiments, multiple steps shown as sequential in this specification can be performed at the same time. [102] Particular embodiments may be implemented in a computer-readable storage medium for use by or in connection with the instruction execution system, apparatus, system, or device. Particular embodiments can be implemented in the form of control logic in software or hardware or a combination of both. The control logic, when executed by one or more processors, may be operable to perform that which is described in particular embodiments. [103] Particular embodiments may be implemented by using a programmed general- purpose digital computer, by using application specific integrated circuits, programmable logic devices, field programmable gate arrays, optical, chemical, biological, quantum or nanoengineered systems, components and mechanisms may be used. In general, the functions of particular embodiments can be achieved by any means as is known in the art. Distributed, networked systems, components, and/or circuits can be used. Communication, or transfer, of data may be wired, wireless, or by any other means. [104] It will also be appreciated that one or more of the elements depicted in the drawings/figures can also be implemented in a more separated or integrated manner, or even removed or rendered as inoperable in certain cases, as is useful in accordance with a particular application. It is also within the spirit and scope to implement a program or code that can be stored in a machine-readable medium to permit a computer to perform any of the methods described above. [105] A "processor" includes any suitable hardware and/or software system, mechanism or component that processes data, signals or other information. A processor can include a system with a general-purpose central processing unit, multiple processing units, dedicated circuitry for achieving functionality, or other systems. Processing need not be limited to a geographic location, or have temporal limitations. For example, a processor can perform its functions in "real time," "offline," in a "batch mode," etc. Portions of processing can be performed at different times and at different locations, by different (or the same) processing systems. Examples of processing systems can include servers, clients, end user devices, routers, switches, networked storage, etc. A computer may be any processor in communication with a memory. The memory may be any suitable processor-readable storage medium, such as random-access memory (RAM), read-only memory (ROM), magnetic or optical disk, or other non-transitory media suitable for storing instructions for execution by the processor. [106] As used in the description herein and throughout the claims that follow, “a”, “an”, and “the” includes plural references unless the context clearly dictates otherwise. Also, as used in the description herein and throughout the claims that follow, the meaning of “in” includes “in” and “on” unless the context clearly dictates otherwise. [107] Thus, while particular embodiments have been described herein, latitudes of modification, various changes, and substitutions are intended in the foregoing disclosures, and it will be appreciated that in some instances some features of particular embodiments will be employed without a corresponding use of other features without departing from the scope and spirit as set forth. Therefore, many modifications may be made to adapt a particular situation or material to the essential scope and spirit.