Jump to content

  • Log In with Google      Sign In   
  • Create Account

DrEvil

Member Since 13 Jul 2003
Offline Last Active Oct 14 2014 07:09 AM

Posts I've Made

In Topic: Crashes When Character Walks

12 August 2014 - 04:47 PM

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.


In Topic: Crashes When Character Walks

12 August 2014 - 03:30 PM

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

In Topic: Crashes When Character Walks

12 August 2014 - 03:29 PM

How big is your leftrect array?

<= 8 looks suspicious

In Topic: A* on large Map

26 December 2013 - 02:09 PM

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?

In Topic: How to split up pathfinding? How to implement divide-and-conquer on pathfinding?

20 December 2013 - 08:48 PM

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.


PARTNERS