Sign in to follow this  

Walkable zones

This topic is 4415 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i'm developing a fast action rpg, something like Diablo or Dungeon Siege. The player control system is simple mouse point-and-click. The artist creates each zone of the world with 3d Studio Max, saving it in 3ds and i load it with my engine. The problem is that i should find a way to check if the mouse is in a walkable zone of the map or not (like on a wall or on a mountain). Basically i dunno how should i divide the map in zones where the player can walk from the ones where he cannot... any advices?

Share this post


Link to post
Share on other sites
One way (probably the least efficient way, but I'm a n00b) I can think of solving this is to associate a 2D map with the 3D one. Also, dependent on how the 3D model is laid out and what engine you're using, it might be possible to check if there's an object at a specifc height and (X, Z) position.

Share this post


Link to post
Share on other sites
In Dungeon Siege, walkable polys in the map nodes are flagged in the modeller. The flags get carried over to the node file format by the exporter. The game engine restricts movement to properly flagged polys of the map.

Share this post


Link to post
Share on other sites
You can generate walkable polys by comparing the normal of the polygon with the world up axis. If they are within some epsilon of each other the poly is walkable. This of course will allow the character to walk to surfaces that are raised, like the top of a statue. Or a flat part on the top of an arch.

Share this post


Link to post
Share on other sites
it's a good idea to use a 2d map, would be faster than flagging all the polys (you need only to check the value of the 2dmap at a particular point, instead of searching the poly where the mouse is pointing to..) and i think it would be a real pain to flag every poly :D

simple question: if i use the "flag method", how should i manage the query? Should i do a ray-triangle check for every visible poly to check which triangle i'm pointing to and then check it's flag, or is there a better way?

Share this post


Link to post
Share on other sites
Notice that the problem is 3-fold: First, how to determine which parts are walkable. Second, which location is picked when clicking w/ the mouse. Third, how to determine a way from the current location to the target location, using only walkable tiles.

So the kind used to store walkability informations has also take connectivity into account, or else the topological problem could not be solved. (Meshes exported from generic modelers seldom solve this problem efficiently by itself.)

The determination of a target location by clicking depends heavily on the kind of playground. Diablo uses an isometric playground, and determination of target is relatively easy. As I remember right, Dungeon Siege isn't isometric and has a more or less free camera, right? Therefore target determination is more complex. Casting a ray would work in all in both situations, but you may need be aware to handle clicking "on" hidden tiles in isometric view.

Using the normal of faces to determine walkability as is mentionend by lubby is good if you do an automatic walkability determination. Due to the fact that nearly horizontal areas on top of the head of a statue are not connected to the area where the PC starts (say there are all surrounding unwalkable parts), the topology already avoids the PC to walk onto the head. So the limitation also mentioned by lubby need not really be an issue besides the things to be done anyway.

Share this post


Link to post
Share on other sites
i think i've found a solution: i'll use the "flag method". Using the opengl selection mode i can easily discover what poly i'm pointing to and then check its flag.

Also, in a precomputation step i can build a grid containing all the map, setting every cell to walkable or not. this way i can use any kind of path-finding algo (i've already implemented the A* and works like a charm) without any problem :)

Share this post


Link to post
Share on other sites
I am kind of new to game programming myself, but your question relates to my own project. What I think I am going to do, and I don't know how efficient this is or not, but on a behind the scenes thing in the game God of War, the way they handled collision with the world was Very simple. They had a model of the world, made in maya, and in Maya they also made the Collision mesh. Wouldn't this be comparable to checking on a 2D map, but better because It can be made in the modeller, and it would be almost as simple (not sure about how processor intensive) as doing the 2d map. Just my $.02.

Share this post


Link to post
Share on other sites
An analogy can be made between the 2d walk map and the collision mesh. The collision mesh would allow for better movement in a true 3D environment. Just simplify (viz. remove) all detail of the wourld mesh, and add in walls where you don't want the player to go. Test world collisions against it, but draw the world mesh.

Which method is best depends on the nature of the game. Dungeon Siege maps are put together like a puzzle from many tileable nodes. There is no collision against most environment entities (trees and such). And there is no true collision with things like building walls. Instead, there is a narrow band of unwalkable polys that border walls. Since the no walkable poly ever meets the wall, you can't go through it.

The collision mesh wouldn't work well for such a pieced-together world. It's better for maps modelled as a solid unit, and I'd imagine it to end up looking like a network of canyon-like tracks.

Share this post


Link to post
Share on other sites
Are you using the 2D map for A* or the polygons themselves? Because you might end up with a whole lot of tiny cells in the 2D map. If you could simply store a pointer to all neighbours for each polygon you can directly use them for the pathfinding. Just set the neighbour ptr to 0 if something is not walkable or seperated by a wall. Could also be used for other things like line of sight, just follow the line through each intersected polygon and check if the side it would leave through is blocked or not (and maybe test all objects within that polygon). Not so useful if the map is very highres and you have more polygons than you would have 2D cells, anyway.

Share this post


Link to post
Share on other sites

This topic is 4415 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this