Run-time Navigation Mesh Generation for 2D Tile Maps

howdoesitwork
  • Run-time Navigation Mesh Generation for 2D Tile Maps howdoesitwork

    I have a 2D tile map, where each tile is marked as blocking or non-blocking. Each tile is 16x16 pixels and sub-tile movement is possible. I'm attempting to generate a navigation mesh from this data, at run-time, using C++.

    Is there any well known library that can be used to generate a navigation mesh, given a 2D tile map? Alternatively, is there any algorithm that can be used to intelligently generate a navigation mesh from the tile data?

    As far as I can tell, all of the popular solutions are aimed at 3D maps and don't perform well when given the simplified case of a 2D map.

  • One idea would be to turn the center points of your tiles into a graph (see your data structures text book), on which any number of pathing/traversal algorithms will work (A*, depth first and breadth first traversals). Given the results, which would be a queue of points to follow, your movement routines can build a smoothed path to follow with splines or simply use LOS checks to get from place to place within that point set.

    Another idea would be to actually use your tile set and build a 3D representation of your walkable squares and feed it to your favorite 3D navmesh generator and library.

    In either case the pixel count doesn't matter as long as you decide on a standard of one tile = 10 units in space (totally arbitrary), just to keep things simple for your math.

Tags
c++ path-finding
Related questions and answers
  • for my needs. Ah and I forgot to mention that nodes can have hierarchy, but this is not a problem if the frame data is reduced. The structure instances don't get duplicated unless any value changes. When... the Diffuse color variation or making it store any value that can change but making it so random that I woulnd't know how to relate the data to the other frames, or need a complex system for it. That's why at this level I prefer to have well-defined data so I can store and work with fast during runtime. It's this complicated because it must support a lot of rendering and animation techniques, must support

  • from it. As an added touch i have made it so after you collide while traveling down the randomly generated map (or rather as the walls move uppward while your character stays put) the X chars you've... saves the data into a vector which represents the console window. It is later used to print the "screen" to the console at a set rate (long double speed), as seen in the for loop after the map drawings...); Insert(lines, i);}; ~Map(){}; /////////////////////////////////////////// generate //////////////////// void generate(){GeneratePath(contents

  • ) is therefore highly wasteful. Then again, making each entity state a singleton hardly seems appropriate. What do you suggest I do? (The same can be said about game states, so whatever the solution to this is, I guess it can be applied to game states as well.) 2. The state of the entity sprite. Most of the time, whenever the state of the entity changes, the sprite that is used to represent it must... work. 1. I noticed entity states are... well, stateless. Basically, they just act on the data in the entity accordingly, they hold no data of their own. When an entity forwards events to its states

  • After spending time today to jot down some notes regarding the implementation of walls into my tile-based game, I've suddenly realized it's not going to be as simple as I imagined before. While..., and whether I missed something or not. Important: a character CAN stand on a tile that has walls, regardless of their form. The common thing for all the three variants: the tilemap will be "kept.... A) The simple approach. Nothing fancy here. Each tile-container can hold not only characters, but one or several Wall objects, which are attached to the edge inside the tile. Pros: easy to implement

  • I'm writing a game engine which is going very fine. However, I'm now posed with handling textures. My Engine is in 2D, for simplicity reasons mostly to get a good idea of how to work with OpenGL. I do this in C++, and I have a hierarchical set-up when it comes to classes. There's a base class and some other classes derive from that. So now I'm onto the part where I want to load up some textures and apply them to polygons. The way my engine works in drawing things is like this: Load up a tile map file and parse it. The tile map contains all the information like events, lights, passability

  • going to use the enet library. I was thinking that each time a game session starts, I push a new Game and I map the client IPs to that table, then I just route messages from those clients... not need any information from the lobby, they see the card table and the data about the other players and so forth. I've programmed the server portion for the game itself. The clients connect to my server object and the server then receives and sends messages; quite simple. The tricky concepts for me are: What's a good way to run many tables at the same time? What's a good way to keep the lobby

  • I'm writing a shooter (like 1942, classic 2D graphics) and I'd like to use a component based approch. So far I thought about the following design: Each game element (airship, projectile, powerup, enemy) is an Entity Each Entity is a set of components which can added or removed at run-time. Examples are Position, Sprite, Health, IA, Damage, BoundingBox etc. The idea is that Airship, Projectile... remove_component(C* c) { components.at<C>() = 0; } void serialize(filestream, op) { /* Serialize all componets*/ } ... }; std::list<Entity*> entity_list; With this design I can get #1

  • This question directly follows on from this one: How can I implement a renderer that can draw many kinds of primitives? I have a small amount of drawing code structured in the following way: A mesh object can be instantiated with different configurations of vertices and indices in order to form any desired shape. A reference to this mesh is then passed to every gameObject class, this class holds spacial information and a draw method that combines this data with that of the mesh to draw that object with the proper transforms. The mesh is simply responsible for holding pointers

  • (); }; #endif If I call Init() from game.cpp, the code works fine, if I call cube->init(), just as this function is entered (not when the other one is left), the device pointer suddenly has an address of 0x00000000. Thanks in advance for any help you can give. Both functions are identical - copy pasted. ...Basically when placed in the same file this works fine, but if placed in separate files (and I have tested this) just after Init() is called, the pointer to ID3D10* device's value is suddenly

Data information