Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

1151 Excellent

About DrEvil

  • Rank

Personal Information


  • Github

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. I definitely understand what it's like to follow rabbit holes. They can feel like the right decisions in the moment(not saying it isn't in your case). My hobby AI bot represents over a decade of hobby experimentation, multiple restarts on various systems, lots of experimentation, ~4 different navigation systems. Bots are one of the few areas of modding that an aspiring A.I. developer could do solo work to get noticed in the industry, and it got me my first few jobs at Pandemic and id Software. It can be counter productive when an actual product is your end goal though. Sounds like you got a pretty big scope planned out. Not sure what your team size is and such, but best of luck with it.
  2. My day job is on http://www.creativersegame.com/ so I'm also familiar with navigating procedural data. Given the voxel nature of our game we haven't had the need or desire to generate any navmesh data, and instead just path on the grid, since much of the pathing looks at meta data associated with the specific block types that are being pathed through, and that would be lost by abstracting it up to a navmesh. Some blocks allow a mob to move over them, others don't, etc. I recently added support for pathfinding for larger than 1 block units. It ended up being relatively simple to get good results, while still ultimately pathfinding at the grid level. The core changes involved doing a loop based check along the horizontal axis to confirm spacing for the desired radius for both clearance as well as whether the node is 'grounded'. It's relatively simple and allows me to maintain the per block logic we use for 1 block pathing. What it the scale of your game that you need to build nav meshes? Even pathfinding within the visible chunk range, we haven't been tempted to try and generate any higher level pathing abstraction on top of the voxel data. If we did, I would probably start with a higher level chunk based graph, but still keep the path following and such at the block level.
  3. There is something super appealing about the manual approach. The quality of output is way more controllable and optimal, in terms of numbers of regions, size of regions, etc, and this even includes a number of manual "special" sectors, like floating "ledge" sectors that I use to cast downwards to make drop connections and such. https://imgur.com/a/rTYiRTB https://imgur.com/a/iUtnE9A Just gotta solve that pesky radius stuff.
  4. I understand, but typically that means layers are built for each agent radius. It's a trade-off of course, but it solves enough of the issues that it is usually worth it for most games out there. Especially when there are freely usable navigation mesh libraries out there like recast. I'm mainly curious what your reasoning is though. I have spend considerable time in the past on my hobby project experimenting with a manually built un-retracted navigation mesh, but it was annoying enough to try and handle the agent radius at runtime that I shelved it. That was many years ago though. For various reasons I've felt like trying to revive it recently, because for my particular use case(a bot in older quake based FPS engines, although I am parsing the collision of the map data to generate the navigation, there is a lot of noise and trash in the output that takes considerable effort to trim out, and still more manual effort to provide contextual information (team specific markup, etc) Here's a really old video showing the tile based recast driven traditional navigation mesh. https://www.youtube.com/watch?v=5qYgRA5oINs Problem is that although I can trim some amount of data from these maps(like brushes marked as sky boxes, etc, even so the resulting data set still contains enough collision data that I get for instance a lot of navigation on "top" of the world, where the brush flags can't be automatically considered relevant or not, even though the navigation inside the world is reasonable, there is a lot of of garbage navigation as well, and enough https://imgur.com/a/r3BbBxn (etf_2fort recast auto navmesh, without hiding a lot of top brush fases you don'e even really see the important navigation of the world) This is another old video of the non retracted navmesh I was experimenting with way back as well, once I got dynamic obstacle support working. There was a lot to like about where this was heading, even though the navmesh was manually built, but I ultimately burned out on compensating for the radius stuff at runtime. There are a lot of edge cases in a real world 3d game map. https://www.youtube.com/watch?v=UhSNwaTV3II I've recently gotten re-interested in my bot and am thinking about giving this approach another go, since after spending a lot of time on the automatic recast drive building, I'm finding that I still have to spend considerable time fixing up the data to trim out data where I don't want it, mark team specific regions, where the resulting time to produce a completed navigation doesn't save much, especially since the manual navmesh creation process is not only very fast with the way I have it set up, but it's very precise and results in far less regions in the resulting data set. Plus I have various shortcuts that take advantage of my problem space, such as the tendency for symmetry in the game maps the bot supports, so I can do half the map and then mirror all the sectors over to the other half. Here's a map where only the green areas have been layed out, and the cyan sectors have been mirrored for the other half of the map https://imgur.com/a/1r1qlYS
  5. Curious why you didn't use the typical nav mesh implementation where the edges of the navmesh are retracted from the walls but the agent radius, so you don't have to do runtime radius compensation? It also nicely handles a set of other problems too, like areas too small for the agent to fit will be culled away from the resulting navigation.
  6. Empty nodes in the tree are to be expected, don't subdivide the structure for empty nodes and it shouldn't be an issue.   If your levels are that predictable though you might be using a more complicated structure than you actually need though.
  7. A grid is a tried and true very simple method. Whatever sized your world is, split it into evenly spaced grid cells and then based on where the viewer is in the world, it's super trivial to calculate the min and max bounding extents of the grid to isolate the small subset of objects that are relevant to where the camera is looking.
  8. I would just give the projectiles a random fake height when spawned and the cover objects and whatever else a value for their max height and allow them to go through when they exceed that. It's simple and it will work consistently for all objects in the scene. The height variation can always be in the 0-player height range. 
  9. DrEvil

    quake md3-help with animation.cfg

    Are you sure the body parts are actually synchronized? That wouldn't be surprising if they weren't synchronized
  10. DrEvil

    Crashes When Character Walks

    What's the value of gPlayer.CurrentFrame when it crashes? Go over the values of all your variables in the debugger when it bombs and you should get a hint.
  11. DrEvil

    Crashes When Character Walks

    Also seems likely you AR accessing your arrays out of bounds with current frame too
  12. DrEvil

    Crashes When Character Walks

    How big is your leftrect array? <= 8 looks suspicious
  13. DrEvil

    A* on large Map

    Something is wrong with your algorithm. 1 second for a 32*32 grid suggests a broken algorithm. You should be comfortably inside 1 second in. A 100*100 or larger easily. Are you profiling in release mode? How are you handling your open/closed lists? Memory allocation?
  14. I work with huge terrains and navigation meshes. We can't even build the entire navmesh due to memory constraints(it uses the popular voxellization techniques), so we built the navmesh in tiles. In order to facilitate long distance pathfinding, which would be extremely slow for long paths, I use the resolution of these tiles as part of the hierarchial pathfinding, which I recommend you do here as well. it's much simpler with tile maps.   The idea is just to group your navigation into larger tiles, and then build a higher level graph on this information. You can do it with a higher level grid or create tile groupings.   http://www.gamasutra.com/view/feature/3000/gdc_2002_polygon_soup_for_the_.php     Depending on the size and complexity of the map, this can simplify the pathfinding hugely. Pathfinding could boil down to a simple search inside the region you are in, and once the search hits the high level sector border, it can skip entirely over all sectors in between, using the cached connectivity of the high level graph. Once it reaches the destination sector, it can fall back down to the tile grid for the rest of the path. Once you have that path through, which includes a mix of high and low level paths, the high level edges would need to be filled in for each tile, but this can be done incrementally as you follow the path. I ended up not doing incremental updates though, because it caused problems such as not having enough path context into the future in order to do my string pulling properly, so I ended up building out the whole path by the time I returned it, but the multi-level pathing is still a huge performance improvement, and filling in those high level sectors is basically a flood fill from the starting polygon/tile until it reaches the next expected high level tile.
  15. DrEvil

    Component design question

    You could also use type_info as the map key and void your own key management.
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!