Hot answers tagged

14

Spatial hashing, quadtrees or octrees can be used to find candidates for the nearest neighbour quickly: and then you can use the loop on that candidate set to get the actual nearest neighbour. Initial Premature Optimization sqrt(n) > sqrt(y) if n > y and n > 0 and y > 0 sqrt(n) < sqrt(y) if n < y and n > 0 and y > 0 sqrt(n) = sqrt(y)...


12

I've done a fair bit of work in this area, although most of my demos are older: (flash 2010) http://genesisbbs.com/appstem.html (click and drag mouse) http://genesisbbs.com/appstem2.html (directX 2006) http://vimeo.com/5206795 I highly encourage you to roll your own, if you are doing this for fun. You will almost certainly need to work with ...


5

I'm not really good at fabricating N- statements, but the minimum search times for an object at child[0] of every child[0] should be close to the same +- a dimension. If the object falls at child[4] of every child[4] the calculation for the octtree could be as much as N^2(?) longer. Since you don't specify how/why the tree is being used, it's hard to give a ...


5

It wouldn't really make sense. Behavior trees have their conditionals at the leaf nodes. Those conditionals determine if the traversal will continue to the other leaf nodes in that parent, or move back up to the other parent nodes. You seem to be talking more about decision trees, where it's expected to have logic in the parent nodes. You can learn more ...


5

This is very nice example of problem suited for A* algorithm. I will not go into details how to implement A* here as it has been done better before and this very easy to find, however this is how I would apply A* for your problem: As you can see, there is only a limited number of states that you can "move" to using single swap (14 for this case if I am not ...


5

Turns out that it was rendered fine in the builds of the project, just not in the debugger in unity. I am planning on reporting this as an error on unity's site, as it was messed up in the debugger only, not the game.


5

Graph drawing is a little more directly relevant than the whole field of graph theory. In particular, I'm a fan of force-based layout. See this demo from the D3 library for an introduction. The basic idea is that you model the graph edges with springs or repulsors, and use a physics integration method to "resolve" the positions of all the nodes. You can ...


5

If you implement the rules from Tic-tac-toe Wiki you can create the perfect AI that always wins, then you can decrease the difficulty by making the AI do random moves, and the frequency of random moves is the difficulty level. Here are the rules: Win: If the player has two in a row, play the third to get three in a row. Block: If the [opponent] has two in a ...


4

What is the ultimate purpose of this algorithm supposed to be? Do you want to generate random roads? Branches for a tree? In 2D or 3D space? The best approach might be to put a bunch of random points on the map, then do a minimum spanning tree. You can then use quadratic or cubic interpolation to make the lines curve into eachother. Alternately, if you ...


4

Sorry I haven't read the linked document. This is how I understand your problem: you have some random points (attraction points) and given a node on your tree, you're trying to find the nearest attraction point? You don't say if this is 2D or 3D but here are a couple tips. The square root. A simple one to implement, don't use the square root when computing ...


4

In A* implementations, this method is commonly completely unneeded, as you maintain an "open list", which is the minheap (note minheap vs maxheap here). Instead of finding out if a node is contained in the frontier, you maintain a list called something like "costSoFar", which maintains a list of the smallest cost for any one node, and check for the node in ...


3

Shogi is well researched, so you should be able to find research papers detailing different methods of implementing pruning or reduction heuristics for Shogi. I can't offer specific advice since I've never implemented a Shogi engine, but I did implement one for Bughouse/Crazyhouse, which has similar rules (captured pieces can be dropped). My advice would be ...


3

Force-directed graphs may be use to create a planar graph embedding in which there are no crossings and each individual node is a reasonable distance (depending on your definition thereof) from each of the others. However there is more to this than meets the eye. A planar embedding is distinct from the concept of a planar graph. A planar embedding is simply ...


3

The main problem with procedural trees is not generating them, but rendering them all every frame at runtime. This is the reason you will see many identical trees in AAA games, it's not that they couldn't implement or write tech that created unique trees, it's that it would mean you'd have to cut out a load of other features for the game to run. If you have ...


3

Personally I would probably start with pre-generated trees and only once I'd have a kick-ass forest rendering engine - complete with bushes, grass, mushrooms and stuff - would I start looking if I need more variable tree meshes. That being said, you could take a look at ngPlant. It includes a GPL procedural tree modeler app, but the libraries that do all ...


2

The need for nodes to be close to each other just rules out any efficient remodelling of your tree structure (otherwise you could use a Red Black Tree which is 'self balancing for example). If you want a binary tree structure you can use a BSP structure or a KD-Tree. Otherwise check out the Octree, the Loose Octree or why not the R-Tree


2

It sounds like you need an octree, binary trees really only work for sorting stuff in one dimension. Note that you still will have to travel down multiple branches to find all objects within an arbitrary zone, no data structure can prevent that. Of course, it would be possible to store items in a standard search tree according to their position on a 3D ...


2

Without knowing the details of your game, I'd say: Keep It Simple. Updating the quadtree whenever something moves is a perfectly acceptable solution. I mention in my answer to a similar question that the simplest way to update the quadtree is to remove the item, then re-add it, but this can cause unnecessary overhead. The way I've done it in the past is like ...


2

I fixed the problem by adding fog with the properties: Color: R: 0 G: 0 B: 0 A: 255 Mode: Exp2 Density 0.03 I know this doesn't solve the problem, but I wanted to use fog in my game anyway and this was an easy solution. I am not going to accept this as the answer since it doesn't actually solve the question, I just wanted to say what ended up working. ...


2

In my experience, navigation should not be handled explicitly in the behavior tree. BTs are great at stateless reactive behavior, while navigation is inherently stateful: you find your path, than you follow it, check whether you should replan... If you need to handle jumps, elevators etc. thnigs get crazy and are difficult to handle in a BT. In all games I ...


2

Contrary to the common belief you can optimize the quad tree function insert. The common implementation of insert, is to traverse from root to the leafs and find the most fit node, in Game programming gems 2 there is an article that details how you can instantly find that node, if you know the extents of the quatree(can be extended to octree) and the extents ...


2

Pip's answer is the right answer but I wanted to add that if you really did need to know set membership quickly and efficiently, you could have added a flag to each node to specify which list it was in. That gives you the extra burden of maintaining that flag's correctness as you move nodes between lists, but the benefit is that you get a super quick answer ...


2

Sure it's possible to use trees! Just to name a few, we use... Quadtrees, Octrees, K-D Trees, and BSP Trees to partition 3D scenes for rendering and physics optimizations, among other uses in speeding up work on multidimensional data. Behaviour Trees for expressing flexible artificial intelligence logic for NPCs. Game Trees for planning by AI opponents or ...


2

With transform hierarchies (trees), the normal method is to work your way up or down the tree, applying any transformations of the parent to the child, at each level, till you have processed everything. Given you aren't concerned with issues like rotation/orientation or scaling, i.e. you're purely interested in translation, it's very simple: //...do your ...


1

The answer is yes, of course. You test object b against all L1 nodes in the root because that's where it is. If a node is hit, add it's objects to the short phase (object to object tests) list. Then recursively repeat the process against those child nodes which were hit. Do this until you determined to hit or miss all leaf nodes.


1

You could use some form of Space Colonisation. Examples ProcWorld and Sea of Memes show growing 'real trees', but could probably be adapted for arbitrary tree structures. Space Colonisation assumes you have some limited area to be filled by a competitive 'lifeform' which grows over one or more iterations. This competitive aspect might not fit what you're ...


1

First, in order for your graph to obey the crucial property of any two edges do not cross, it must be a planar graph. A tiny tutorial on the graph drawing topic is given here. Using force driven layouts may not guarantee convergence to a planar graph: (for example, if a vertex is inside a face, apply an elastic spring force and push the vertex outside the ...


1

I'm guessing that insert and remove traverse the quad tree from root to leaf, and that's why you are concerned about its performance? (By the way, rule of thumb is never perform any optimisations unless you've asked "have I measured a real performance problem" and can answer in the affirmative.) In games, the vast majority of movement would be continuous, ...


1

While it is, of course, possible to implement animations within an AI architecture, it would be a poor methodology for a number of reasons. One such reason would be an agent that chooses to walk but cannot for some reason. Another reason would be needless complexity (many decisions would have to implement an exact-copy of an animation node because they ...


1

I stumbled across tree[d] some time ago... I used it for only a small amount of time to test a project but that was only because I stopped development - the tool gives you a wide range of generator options to play with and, from what I remember, is quite fast. A link is below. The downside is that it isn't a tree generator that you can incorporate. You'd ...


Only top voted, non community-wiki answers of a minimum length are eligible