Hot answers tagged

6

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

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

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 ...


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

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

This paper is actually set up pretty oddly, most CS papers I see are, well, more succinct and to the point? This one kind of rambles doesn't properly label headers and doesn't go into what it is actually doing until section 3 and the appendix. You'll need to learn how to read these papers if you want to use these algorithms, so if you have problems with the ...


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

Techtreejs might be what you are looking for. Here is a demo.


1

When you do set the arrays, here: func duplicate_values(originator:Route): origin = originator.origin destination = originator.destination totaldV = originator.totaldV totalt = originator.totalt dVBudget = originator.dVBudget tBudget = originator.tBudget tdVRatio = originator.tdVRatio nodes = originator.nodes # <- here ...


1

I would implement a Z level system: create a draw_texture function that takes the Z level of the object (which could be determined by its position), and instead of rendering, store the texture and src/dst rects in an array representing the Z level (you could have one array for each level, or a matrix, where each row would be a Z level). Then create a ...


1

Looks like its a handedness issue, in 3d graphics the choice of which axis is called what is kind of arbitrary (to a point) and there are a couple of different common standards. Unity uses the left-handed, Y up, but other software, particularly 3d modeling software like blender, use right-handed, Y or Z up. Freya Holmér made this really great reference image ...


1

I would say game assets is definitely not specific enough. Everything in your game is an asset — the terrain itself, the shaders and textures it uses, every JSON or XML data file. Similarly, I'd argue props is also too broad. A chair or a sword could reasonably be called "props" too, but they're not scattered terrain items like you're describing. (Though ...


1

Found an answer here. I thought a behaviour tree should start at the last running node to start computation time but that lead to the problem stated in the article. Treating Running States One common question when implementing a Behavior Tree is that: what to do in the next tick after a node returned a running state? There are two answer to it: starting the ...


1

As the nodes are just Actors, you could place you node content (the labels and sliders) first in some container like Table or Container and give the actual content a bit of margin in that wrapper container. After you explanation about what you want to achieve the above won't work as you want to move the plus and minus buttons that are used to expand and ...


1

I suppose it's just the usual trade off. You'll have to decide, based on desired effectiveness of the selected strategy and performance in terms of how long your tree search takes, what you want. You have to decide how many moves into the future you want to take into account, and then you prune on the resulting tree as usual. Your example of playing 5 bad ...


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

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

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

When working with a relatively small number ( < several thousand) of smallish objects (most objects aren't big enough to potentially collide with a lot other objects) I find that a simple x-ordered list of axially aligned bounding boxes (AABBs) works pretty well. I just put the objects in a list, then each frame after moving the objects, I quick sort the ...


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