next »

[accordionfolder]

I'm at a stumbling point here. I'm trying to convert a 2d map (50x50 pixel buckets actually) to a quad tree with random access for use with path finding. That is, I'm in point 3,3 I need to randomly access that point in the tree, preferably w/o iterating through it (ala binary heap implemented as an array), is there anyway of structuring a tree in that fashion?

Thanks!

[David Pittman]

It's been a while since I've seen a binary heap array implementation, but don't you still have to traverse the tree to access leaf elements? The advantage to the array implementation is just that you don't need to store pointers; you simply have the one array and can access child elements by arithmetic on the array indices. You could certainly structure a quad tree that way too (any node with array index i would have children at 4i+1, 4i+2, 4i+3, and 4i+4), but that wouldn't provide random access to leaf nodes. What you would know is that all your leaf nodes were at the end of the array in a determinate order, and given a known tree depth, you could compute the index for any (quantized) 2D location, or perhaps precompute a table of indices. But I'm not sure that's going to be worthwhile.

Alternatively, you could lay out your 50x50 leaf nodes in their own flat array and point to those elements when building your quad tree. Then you'd have random access to the leaves (and only the leaves, but I think that's fine for your case), and you could also traverse the quad tree to those same nodes when you needed.

[BorisTheBrave]

Could we get some clarification on what you are trying to do, it's not so clear. What do you want/use the quad tree for?

As David Pittman points out, there's a simple 1-to-1 mapping between leaves of an n-ary tree and a 1d array. If you need random access to leaves, make an array of pointers to the leaves. But I cannot think of a circumstance where that is useful where taht doesn't negate the point of having a tree.

Perhaps you mean a sparse quadtree, to efficiently represent large blocks of solidity? You could still do a similar thing with a 50x50 array of pointers, each to the node that covers that point in the image.

[accordionfolder]

Sorry for the lack of clarity in my post, up too early I suppose. For clarification, I'm working on a 2d game. The game "map" is split into 50x50 pixel buckets (spatial hashing) for efficient collision detection and drawing. I'm currently working on implementing a path finding element for the AI and assume that a tree structure will work best (each node in the tree equates to a bucket on the map). To simplify my problem I am only using quad trees for now (as opposed to oct-trees).

THE PROBLEM:
So I have an enemy in bucket (x,y) and want to form an efficient path to the player. How can I structure the game architecture or the data structure itself to go to that point within the quad tree and start a simple path finding algorithm? I apologize if this a simple question, my experience in AI design is limited.

I have been pondering, I guess I could simply, when initializing enemy units, give them a pointer to a node in the tree. When changing buckets it could simply update it's pointer. Otherwise I may have to traverse the tree to find the appropriate point.

IF you have a better plan or paradigm for approaching this problem I will not be offended in the least if you offer it.

Thanks for your continued assistance.

[accordionfolder]

And your also correct on the random access within a binary tree, my mind is not all together there 

[george]

So I have an enemy in bucket (x,y) and want to form an efficient path to the player. How can I structure the game architecture or the data structure itself to go to that point within the quad tree and start a simple path finding algorithm?

apologies for what may be a obvious question, but why does pathfinding relate to spatial partitioning?

[accordionfolder]

Each "bucket" (50x50 square) which is a result of spatial hashing, is equivalent to a node in the search tree. That is all.

So when path finding, an enemy will map it's path through the buckets represented by the nodes in the tree.

[Dacke]

How are these buckets placed and stored? Is it just a grid covering the rooom? 

I'm not sure if this applies. But there is nothing wrong with having parallel data structures, if you need to. For the path finding, you can store the buckets in a 2D-array. For the tree-thingy, you can keep the tree. Just have the same bucket-objects in both the array and the tree, so that you don't store the data in two different places.

But again: I'm not sure how the tree stuff works in this case. There may be a better way to do it.

[accordionfolder]

The buckets are a 2d array of small sized lists (the max # of enemies that could fit is 4), barriers are stored using a 2d array of chars simply because it only needs to know what kind of barrier to draw at a certain point and no other information, so storing a heavy weight object doesn't make sense.

So making a paralleling (is that even a word... spell check thinks so) set of data structures would not accomplish much.

I think I may resort to using a 2d array of some manor, easy for random access to the points I require. It just seems more difficult to implement a least cost A* in that way.

Oh path finding, you hurt my brain....  

[Dacke]

Wow, I really don't think we are understanding each other

Heavy weight objects? What?

[accordionfolder]

You guys manage to zero in on the unimportant details of a sentence, huh?  

I was simply stating that, while I could store my obstacles as a type of object (as I do with the enemies), a primitive such as a char is much lighter "weight." That is 1 byte is preferable to whatever memory is consumed by even the most mundane of objects.

BUT, that is completely irrelevant. I was simply noting that paralleling the buckets data structure to a tree wouldn't yield the desired results. It may be viable to do so with the 2d array of chars though.

[Dacke]

Picking on details is not what I was doing!

If I understood you correctly, you have a number of properties that belong together (a few chars and a list of a few enemies). It's common practice to make these into an object. It gives you a few bytes of overhead, but makes things much more manageable.

The reason to use trees and arrays etc. is often not to save space. The big advantage is that you can find the things you need, when you need them, in less time. If having two parallel data structures helps you accomplish this, it's a big win.

But I'm not sure what you are using your trees for, so I can't say I'm right on this. It's quite likely I'm completely wrong. But I'm not just picking on your choice of words, I'm trying to understand what you are doing. Honestly!

[raigan]

I don't think you need a tree; if you have a grid of tiles that should be good enough, right? Spatial hashing should be sufficient for mapping a given position to a particular bucket.

A* or whatever just needs a graph to search on, and a grid is implicitly a dense graph (where each cell in the grid is a node, and nodes are connected to 4 or 8 neighbour nodes, depending on whether you allow diagonal movement).

Possibly I'm not understanding, there seems to be a lot of confusion..

[BorisTheBrave]

You seem a bit trigger happy with datastructures. They are a means to an end, not visa versa.
You want to do A* pathfinding. I, like Raigan, don't see the need for a tree at all - A* can work fine on a grid, better even. I think this is the source of the confusion for many. As I asked before, what do you expect to use the tree for.

Anyway, perhaps this conversation should have ended at post 4 - I don't think there's any answer other than exactly what you describe, keep a pointer to leaf and maintain it as you go about your business.

[accordionfolder]

Yes sir, I do understand that it is possible to implement path finding with really any graph, but it has found a more simple (i.e. easy for me to visualize and implement, this is personal preference) and wide spread application implemented via trees.

Somewhere in the heap of confusion I posted that I may choose to implement the path finding via the afore mentioned 2d array. It seems that the general consensus agrees with this plan of attack. 

@Dacke - I was just messing around, no harm done what so ever. I keep making assumptions that it is impossible for others to completely grasp w/o digging through my code, I think I will edit the top post to rephrase my issue at a higher level to gather some more input on my specific problem.

As always, continued input is appreciated. To all those who have already posted, thanks for your added ideas and thoughts! It always help me clear my head to explain what I am trying to accomplish to others.