Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your help!

We need 7 developers from Canada and 18 more from Australia to help us complete a research survey.

Support our site by taking a quick sponsored survey and win a chance at a $50 Amazon gift card. Click here to get started!


Member Since 06 Apr 2007
Offline Last Active Private

Topics I've Started

About Quadtree (spatial partitioning)

Yesterday, 08:26 AM



I am wondering how do I identify which node is walkable.

Say when I first break up a tile which covers the whole scene into 4 divisions.

And there are heaps of obstacles in the leaf node, how can I tell the obstacles are located in there

I am using DX9, D3DX....



BTW, how do I use AStar or TimeAStar with QuadTrees?



Hybrid approach of data structure representation of opened list

27 August 2015 - 03:52 AM



After taking a read on this page,

Amit has suggested to use a

priority queue for ranking management

binary heap for insertion and deletion of opened nodes.


I wonder, if I create 1 std::vector and 1 std::priority_queue in my astar class.

How can I make sure there is actually 1 centralized opened list available.

If 2 inconsistent opened lists are available, they may expose to errors.

Any code example on how to go about doing that?

To keep 2 containers synchronized?

I am a C++ coder.




I'd like to have a data structure that excels at insertion, deletion and looking up?

Which should I choose? I find out that heaps can only have O(n) on minimum + maximum search

My map is about 40x40 cells (a grid)



How to generate a grid for a 3D game?

24 August 2015 - 09:22 PM

I need to build a grid auxiliary to the normal navigation mesh.

* For 1 or more than 1 unit radius

* Aligning to obstacle boundaries

* may be built offline (built from the navigation mesh?)


Are there any good tutorials on how to go about doing that?



.x file: How to use loops to traverse the tree structure

21 August 2015 - 10:24 PM

I probably cannot get the number of children within that structure.

I mean the hierarchy because it isn't a member variable in the D3DXFRAME structure.

I sometimes would want to iterate a lot of frames, Is it an absolute thing to do it by recursion,

because I am getting stack overflows. I got about 50000 custom frames, so the C++ program cannot hold

that many frames on the stack by recursion, which is quite unsatisfactory.

Any ideas I can work around this?



How to load a custom d3dx frame?

20 August 2015 - 05:34 AM

xof 0303txt 0032
template Frame {

template ActualCostTblEntry {
 <aaaaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaa>    // intentionally changed
 DWORD fromX;
 DWORD fromZ;
 FLOAT cost;

Frame Root {

 ActualCostTblEntry Entry {
HRESULT d3dAllocHierarchy::CreateMeshContainer(
    LPCSTR Name,
    CONST D3DXMATERIAL *pMaterials,
    DWORD NumMaterials,
    CONST DWORD *pAdjacency,
    LPD3DXMESHCONTAINER *ppNewMeshContainer)

    *ppNewMeshContainer = NULL;

    d3dMESHCONTAINER *pMeshContainer = new d3dMESHCONTAINER;
    ZeroMemory(pMeshContainer, sizeof(d3dMESHCONTAINER));    

    *ppNewMeshContainer = pMeshContainer;
    pMeshContainer = NULL;

    return S_OK;
d3dAllocHierarchy Alloc;

    if (SUCCEEDED(D3DXLoadMeshHierarchyFromXA("data\\costs.x",
        D3DXMESH_MANAGED, d3d::m_pDevice, &Alloc, NULL, (LPD3DXFRAME*)&m_fActualCost, NULL))) {


    for (d3dFRAME* f = m_fActualCost; f != NULL; f = (d3dFRAME*)f->pFrameSibling) {
        d3dMESHCONTAINER* mc = (d3dMESHCONTAINER*)f->pMeshContainer;
        if (mc) {
            DWORD fromX = mc->fromX;
            DWORD fromZ = mc->fromZ;
            DWORD toX = mc->toX;
            DWORD toZ = mc->toZ;
            float cost = mc->cost;

            AStarNode* from = Coordinater::m_AStarNodePool.acquireNode(fromX, fromZ);
            AStarNode* to = Coordinater::m_AStarNodePool.acquireNode(toX, toZ);

            AStarNodePair *np = new AStarNodePair(from, to);

            m_ActualCosts.insert(std::make_pair(np, cost));


How should I put the cost data into the mesh container in CreateMeshContainer method?


As I think back, should I put the variables in the frame class instead?