# Tag Info

## Hot answers tagged graph

34

This is caused in the history. Early computers had Cathode Ray Tubes (CRTs) which "draw" the image with a cathode ray from the upper left corner to the lower right. To ease the interface between the graphics card memory and the CRT the memory was read from the beginning and the image was drawn from the top left (with the lowest memory address) to the lower ...

15

The problem is with how you are formulating your navigation graph. If you'll allow me to butcher your diagram: Here is what the navigation graph should look like. For each node in the original graph with n edges, where n > 1, it should be replaced with n nodes. (Notice that each node in the graph is connected by two edges.) Inserting start and end nodes ...

12

What you want is to produce a dual graph; that is, a graph produced by converting faces to vertices, and connecting them based on adjacent faces in the original graph. Example: The problem, as you can see, is that if you want to keep the same layout of the graph, you'll get some really curvy edges in the dual graph. Also, you'll often end up with a ...

11

Have you actually tried a hierarchical graph and measured the performance? Have you investigated simple physics engines to see how they handle the problem, even a 2D engine that has linkage between objects would help guide you in a proven direction. I would not try to run your physics in multiple spaces, the complexity would be daunting. Run the physics ...

9

That is a neat demo. The best reference for Delaunay triangulations and Voronoi diagrams that I've found is Jonathan Shewchuk's book and lecture notes. The book is significantly more advanced than the lecture notes, and talks more about mesh refinement. I suggest you start with the lecture notes. Do you need to go to grad school to generate a Delaunay ...

8

When traversing the graph, always turn the same direction. You can use cross product to check what is the left or rightmost direction in a junction.

5

Keeping things simple I don't know the exact context of your problem, but I give below the most accurate solution possible given the specific question you've asked. However, if you want to keep things simple, it is better to construct the graph yourself. In that way, there is no need for you to identify subgraphs, since in creating them within a larger ...

5

You may not want to use a graph, but ultimately the problem is one of planar 6-connectedness. I challenge you to find a simpler and better-suited structure than a graph for this :) I wouldn't be intimidated by the data structure for this -- when you consider how trivial the implementation will be, it's not like you'd be writing Boost Graph Library all over ...

5

A* doesn't really care about the shape of the graph you're using. Let's see the pseudocode for A*, stolen from Wikipedia: function A*(start,goal) closedset := the empty set // The set of nodes already evaluated. openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node came_from := the empty map ...

5

You're misrepresenting your graph. What you really have is something more like this: Where the red dots are your nodes, and the blue lines are your edges. This can be produced by creating four nodes for every node in your current graph. (There are actually even more edges that would be valid here as you could move diagonally between a number of these ...

4

Looking at your image gives an idea of how this should work. Two points are apparent: Endpoint nodes (those with only one connected neighbour) are the least likely to have checkpoints, since they share with the fewest other nodes; endpoint nodes will in fact only contain a checkpoint iff they are isolated as a degenerate DAG, i.e. they have no neighbours ...

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

Use the tween engine. (tweening) It is very powerful and easy to use. You can create animations for any atribute, timelines with simultaneous and/or sequencial animations, and assign callbacks for starting, ending, looping, etc.

3

Perhaps I´m over thinking it. Yes, you are. Transformation being done in shaders is meant to be literal. "Transformation" in this case being the application of some transform to the various per-vertex attributes. Where that particular transformation comes from is generally irrelevant to the shader. It is given a transformation, and it applies it to the ...

3

I believe the solution is simple - mark vertices of the path as impassible and run regular Dijkstra for this input. If it fails to find a path you are sure they are on different sides. Edit: If your path does not split the graph into two components you can still use method described above with only difference - after finding the shortest route check whether ...

2

Finding connectivity in a general graph is usually done with floodfill-style algorithms (i.e., breadth- or depth- first search and variants thereof) anyway, so I don't think that abstracting out the process in the way you're describing is actually any great help. Instead I would maintain the core data structure in a grid; there are very standard approaches ...

2

Using a simple 2D array works. Then you don't have to walk a graph to get somewhere. Deciding what should fall next is as easy iterating up the current "column" of the array you're in. You can easily step into the grid anywhere with the x/y coordinates and do your collision detection or whatever you need to. That means you can get neighbors in constant ...

2

Model, View and Projection matrices are passed as uniforms to the vertex shader, which uses them to transform vertex coordinates and normals. Typically projection matrix is constant between frames, view matrix is calculated once per frame and model matrix is unique for each object. Model matrix is in world space. This is of course not the only way to do ...

2

Update solution: Even though I was inspired by Andrew Russell's solution. For anyone interested. I've solved it in the end as such. 1) I first detect intersection (point I) with graph (or multiple graphs afterwards). 2) Then I find point in angle higher than angle from an incoming point (Intersection -> Start). Such point is marked yellow. I'm only ...

1

Addendum: Early graphics were done on vector monitors, just one step up from the oscilloscopes seen in the lab where (0,0) would be in the exact middle of the screen, subject to some knob turning to set X/Y scale, X/Y offset, and possibly X/Y inversion. The dedicated hardware of Atari "Asteroids" (1979) for example used a vector screen; it would be ...

1

Not everything is top-left. OpenGL, for example, specifies that the origin is at bottom-left, and this is pervasive throughout the API: texture coordinates, viewports, texel rectangles, the standard ortho projection: it's bottom-left all the way. There is a difference in thinking here. On computer screens, as with books, when people read (and I'm assuming ...

1

This is a great question that I've thought of many times. The simple answer to "why" is because TV formats also drew their lines from left-to-right then top-to-bottom. Original computer monitors were CRT screens (small TVs), so the format naturally stayed the same. When monitors became flat screens (and TVs became flat screens too), it was equally natural to ...

1

It sounds like you are looking at an unusual problem for games: given a bunch of rectangles with connecting edges, lay them out so that no rectangles or edges (I'm guessing) overlap. Usually the layout happens during map generation, which means it's trivial. The general problem, of laying out a planar graph with a set of goals (minimise overlaps, edge ...

1

This took some figuring out for myself, but I've got one for you. Note that in the if statement we have no changes to path (since nothing is removed from it). Now edge2 is changed it it's next every iteration, removing the need of the else statement. I added nextEdge1Spot to avoid checking whether an edge has been deleted or not. public static LinkedList&...

1

Your code only makes a single test with edge1 before advancing. This skips over certain nodes that are in a straight line. For example, if you have 5 points (A->B->C->D->E) all in a straight. The smoothed path should only contain two points (A->E). In your logic you test if you can travel between A->C and if you can then B is eliminated. You then check ...

1

1. Detecting a loop of tiles The problem seems similiar to detecting a cycle (loop) in a graph, see here or here. The set of nodes V of that graph G=(V, E) are the tiles, an edge e = (v1, v2) exists between two different nodes, if the tiles are direct or diagonal neighbours 2. Handling the screen border case The screen border consists of those ...

1

You can create an algorithm based of edge intersection. The idea is to draw a line between the two points called a ray. This then acts as a line to test whether the polygons lines intersect. You can do this in pseudo-code: // Method in point: bool IsPointBehindPolygon( testPoint, polygon) { originPoint = this; ray = new Line(originPoint, testPoint)...

1

Here's the algorithm I see happening in your question: (I use "inside" meaning specifically not ON the cut line but only inside it) P = Plane To Cut Across. For every edge in the graph as Line A->B { A_inside = Is point A inside plane P? if (point B is on line P && !A_inside) return nothing; B_inside = Is point B inside plane P? ...

1

The only algorithm I've found for solving this problem is the constrained Delaunay triangulation algorithm discovered by Paul Chew (http://www.cmlab.csie.ntu.edu.tw/~plokm/htdocs/cmlab/%B1M%C3D/triangulate/Constrained%20Delaunay%20Triangulations.pdf ). As in the case of the classical Delaunay triangulation, the complexity is still O(n log n), which is ...

1

I have been in the same situation as you and this is how I solved it. Before that, some clarification: In my SceneGraph each SceneNode keeps track of its own local transform (scale, rotation, translation) and a concatenated transform (world). SceneNodes can have multiple components. BEPUPhysics is the physics library being used, its entity transforms are ...

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