Graph is an data structure for a set of objects where some pairs of the objects are connected by links.
3
votes
0answers
26 views
Convert 2d generated level to graph or analyze
Do you have any idea how to extract graph data from this type of procedurally generated level?
Well, actually we need to analyze only top level (gray). Background (black) does not matter. What I am ...
0
votes
0answers
84 views
How to draw projectile arc between point A and point B
I don't need any physics computations.
I just need to draw a parabola between two points in 3D.
I have already drawn a simple example from point A:
for (float param = 1; param < 3000; param += 2)
...
0
votes
0answers
13 views
Filtering the target for lights
I'm in process of writing my own 3D engine in WebGL using assets of one popular game. I do not use any existing graphing library(no Three.js or others), I operate with pure WebGL calls. I managed to ...
0
votes
0answers
23 views
Converting a graph of relative node locations and edges to a game map
I'm using a project called metazelda (https://github.com/tcoxon/metazelda) to generate a graph of nodes with edges. I'd like to take this graph, and use it in the generation of a level in my game ...
3
votes
1answer
78 views
Multilevel 2D grid graph and A*
I've coded up a little grid based dungeon game. Everything working quite nicely in a Tile[,]. The AI uses basic GOAP for tasks and A* for moving around. Tile reachability is done using a floodfill.
...
1
vote
1answer
104 views
What's an optimal procedure to create a connected cyclic grid of nodes and edges for A* pathfinding
like the title says, I'm trying to create a grid of nodes that hold edges or connections to each other so I can perform A* algorithm to have objects traverse across them as seen in your standard RTS.
...
4
votes
1answer
62 views
Lazy way to figure out the two sides of a border?
We have a 3d model. There is a simple path on that model's surface graph G of the form:
<v_0, v_1 ... v_n-1, v_n> where if v_i == v_j then i == j
Great! now the simple question appears:
How ...
2
votes
1answer
116 views
Storing visibility graph for path-finding: do redundant and non-visible pairs of points have to be saved?
Using C# in Unity, I have recently implemented an algorithm that determines during run-time the visibility graph of a given scene in my game project (visibility between corners of obstacles). Now I am ...
3
votes
1answer
524 views
How to choose and scale heuristics for A-star on a graph?
I am trying to find the best and scale my cost function for my algorithm. I am following amit blog which explain that (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-...
2
votes
1answer
99 views
HeightMap from a graph
This is just a toy experiment.
I laid out a graph in 2d space, so that every node has x and y coordinates. I'm considering degree of a node as a height value at position x and y of a height map.
I ...
7
votes
3answers
247 views
Graph search with a high number of actions
I have implemented A* to reach a goal state from a start state. My state is position X,Y, angle and others state variable. I have a number of actions.
What I call actions is : A* on a grid has 4/8 ...
3
votes
1answer
363 views
How to implement visibility graph pathfinding in Unity/C# to detect paths (i.e. visibility connections) efficiently?
I am struggling with implementing continuous path-finding trough visibility graphs. Notice, I know that grids can be used even when movement is not trough grids (e.g. Theta*). But for my current needs,...
0
votes
1answer
66 views
Camera (pole cam) implementation problem
In my project I have simple scene graph to render whole scene and Bullet physics SDK to provide physics simulation.
Each rendered object is represented as scene node. Camera always has target and ...
7
votes
2answers
430 views
How to create a map from graph
I want to draw a 2d polygon map based on data provided by another source to ease analysing actions on the map. The data has the following format:
1 ['2', '4', '5', '7', '17', '10']
2 ['1', '3', '4']
...
6
votes
4answers
159 views
Evenly distributed checkpoints in a procedurally generated world?
Got a procedurally generated world. It's succinctly described as an undirected acyclic graph where vertices are junctions and edges weights/length note the amount of time/effort guesstimated to be ...
1
vote
2answers
350 views
Bubble shooter clone, structure for storing/adding of bubbles
Im having a few issues trying to figure out what the best data structure to use for storing bubbles on the grid, and how to connect new bubbles to the grid when a moving ball collides with a ball on ...
0
votes
0answers
76 views
How to combine embedded generated graphs in a finite 2D plane?
I'm pretty new to working with graphs but I'm looking at using them to create the world map for our game (a text mud with rooms/nodes and paths/edges between rooms). There are a number of interesting ...
1
vote
1answer
191 views
Understanding Scene Graphs and Graph Edges
So I'm trying to getting to grips with using Scene graphs and nodes in my code (game coding in C++) and I think I understand the basics of them and how they are used (and I can definitely see the ...
2
votes
1answer
152 views
Voronoi / Delaunay Graph - Triangle Circumcenter error
I have written a Delaunay Graph script that given a set of points (voronoi cell/region) will generate the Delaunay triangles with their edges. Considering that the Voronoi diagram is complimentary to ...
6
votes
3answers
1k views
How to find path in graph without crossing the walls?
I would like to know how to find path in a graph while having the edges "double-sided". Consider this scenario:
I have list of the line segments. These represents "walls" or rather impassable edges (...
24
votes
5answers
11k views
Why is the origin in computer graphics coordinates at the top left?
From what I've seen almost all things use coordinates where (0, 0) is at the top left and the positive Y-axis goes in the downwards direction of your screen.
Why is it like this? Why not the ...
2
votes
1answer
294 views
Algorithms for positioning rectangles evenly spaced with unknown connecting lines
I'm new to game development, but I'm trying to figure out a good algorithm for positioning rectangles (of any width and height) in a given surface area, and connecting them with any variation of lines....
1
vote
1answer
119 views
More Precise PathSmoothing
I'm reading a book about AI - Path planning and path smoothing. Yet this book is using c++ code. And i'm coding in c# with the XNA framework.
I have a path smoothing working, yet the book says it can ...
0
votes
1answer
115 views
Path smoothing while path following
I can't find a nice way to do path smoothing while i'm following a path.
I have tried this piece of code but aparently it doesn't work as suspected.
The idea of how it should work is:
Edge 1 (the ...
8
votes
3answers
2k views
Determine if a set of tiles on a grid forms an enclosed shape
Given a set of tiles on a grid, I want to determine:
If the tiles make an enclosed figure
If the tiles make an enclosed figure when you count the sides of the board as an edge of the figure
If either ...
2
votes
2answers
182 views
How can I test if a point is behind a polygon in 2D?
In order to improve the performance of my visibility graph generator I am trying to figure out the following.
Given the image below; is there a way to find out if a point is 'behind' the polygon? For ...
0
votes
0answers
47 views
Checking if two lines are crossing [duplicate]
How can I check if two lines (created with function love.graphics.line) are crossing themselves? I may use this ability to create procedural maps via graphs.
2
votes
1answer
82 views
How can I cut a graph representing 2D positions into two sub-graphs?
I have a graph where each node is associated with a 2D position. I would like to use a finite line to "cut" this graph into two halves, as shown below:
Note that the cutting line does have a ...
2
votes
0answers
105 views
Graph Isomorphism > What kind of Graph is this? [closed]
Essentially, this is a variation of Comparing Two Tree Structures, however I do not have "trees", but rather another type of graph.
I need to know what kind of Graph I have in order to figure out if ...
3
votes
1answer
635 views
Placing nodes in a graph in a random but readable way
I'd like to create a simple map from vertices and lines - you know, like a usual graph. A tree, to be precise.
To select the location of the next point that comes from one, I use a simple circle-...
6
votes
1answer
2k views
Delaunay triangulation. Where to start?
I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot ...
5
votes
1answer
375 views
Triangulating a partially triangulated mesh (2D)
Referring to the above exhibits, this is the scenario I am working with:
starting with a planar graph (in my case, a 2D mesh) with a given triangulation, based on a certain criterion, the graph nodes ...
2
votes
2answers
257 views
State propagation in modern OpenGL
When last I dabbled in game development, I managed my geometry in a tree. Every node would call the render method on it's children, prior to resetting it's transformations, thus allowing the ...
5
votes
1answer
344 views
A* for non grid network
For my specific case, I am trying to find a path finding implementation similar to what described here.
I could see reference implementation for A* and HPA*, but I wonder how to extend A* to simple ...
2
votes
3answers
1k views
Integrating Scene Graphs and Physics Engines
For some specific reasons, i will have to use a graphic engine based on Scene Graphics with a Physic Engine without this concept.
I was thinking about a clear way to integrate both representation but ....
2
votes
1answer
2k views
Moving sprites on a graph in libGDX
In my game I'd like to move sprites on a fixed path. Until this point I was trying to stick with the tools already provided by libGDX, like the Tiled map renderer classes so I'm looking for a solution ...
2
votes
2answers
212 views
Splitting Graph into distinct polygons in O(E) complexity
If you have seen my last question:
trapped inside a Graph : Find paths along edges that do not cross any edges
How do you split an entire graph into distinct shapes 'trapped' inside the graph(like ...
5
votes
1answer
176 views
trapped inside a Graph : Find paths along edges that do not cross any edges
This is a graph based platformer level and the round shapes are creatures.
I am looking for a path traveling along edges that does not cross other edges(To simulate the creature crawling on the ...
2
votes
2answers
2k views
Data structure for bubble shooter game
I'm starting to make a bubble shooter game for a mobile OS. Assume this is just the basic "three or more same-color bubbles that touch pop" and all bubbles that are separated from their group fall/pop....
6
votes
1answer
7k views
C# graph library to be used from Unity3D [closed]
I'm looking for a C# graph library to be used inside Unity3D script.
I'm not looking for pathfinding libraries (I know there are good one available).
I could consider using a path finding library ...
2
votes
1answer
319 views
Is finding graph minors without single node pinch points possible?
Is it possible to robustly find all the graph minors within an arbitrary node graph where the pinch points are generally not single nodes? I have read some other posts on here about how to break up ...
0
votes
2answers
404 views
Partial recalculation of visibility on a 2D uniform grid
Problem
Imagine that we have a 2D uniform grid of dimensions N x N. For this grid we have also pre-computed a visibility look-up table, e.g. with DDA, which answers the boolean query is cell X visible ...
4
votes
1answer
2k views
Find sub-graphs in a graph
The initial problem I'm trying to solve is for pac-man, but of course there must be thousands of other situations with the same problem. I consider the pac-man grid to be a graph (two ways of doing ...
3
votes
1answer
763 views
Better data structure for a game like Bubble Witch
I'm implementing a bubble-witch-like game (http://www.king.com/games/puzzle-games/bubble-witch/), and I was thinking on what's the better way to store the "bubbles" and to work with. I thought of ...
10
votes
1answer
3k views
To scene graph or not to scene graph?
I've been struggling with a decision regarding whether or not to implement a scene graph in my game. I have some use cases that call for such a tool, but I haven't been able to get through some of the ...
5
votes
4answers
1k views
Dynamic Dijkstra
I need dynamic dijkstra algorithm that can update itself when edge's cost is changed without a full recalculation. Full recalculation is not an option.
I've tryed to "brew" my own implemantion with no ...
