Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

A graph is a data structure for a set of objects where some pairs of the objects are connected by links.

0
votes
0answers
15 views

Returning a placed structure to inventory, then placing it back down retaining its' contents

I'm making a mod for Ark Survival Evolved and I'm trying to come up with a variant to the pickup feature. I want to be able to keep the structure inventory upon returning it to the players inventory ...
0
votes
0answers
17 views

Diagonally iterate in reverse each item in a rectangular 2D array [on hold]

How would a loop be constructed to iterate all items of a 2D array in reverse, and diagonally? For example, iterating in that way with the following 2D array, would output the result below: 2D Array ...
5
votes
1answer
163 views

How to randomly create a fair maze for a multiplayer game?

I am creating a 2d multiplayer RTS game which happens inside a maze. I have used Growing Tree algorithm to randomly generate the maze. I thought that the maze would be fair for each team as long as ...
0
votes
2answers
100 views

Coloring a Voronoi Graph

Intro: I want to convert a Voronoi Graph made with this awesome library by jceipek on GitHub into something I can work on. So far so good, this user provides with a demo to start with and shows how ...
2
votes
2answers
109 views

Find extreme points of a rotated ellipse function on a given axis

How to find the points where it is most extreme on the X and Y axis? For example lets say I have an equation that describes an ellipse that is rotated: ...
1
vote
2answers
93 views

What graph Search algorithm (s) that can simulate the behaviour of a human searching in a forest

We are building a game , where a group of humans(AI agents) have to wander seperatly throughout the forest looking for a collectable item. The forest is represented as a 2d graph with the item ...
1
vote
0answers
268 views

Shadow & sorting issues with vertex colored PBR Shader Graph

I'm working on a custom shader using Unity 2018's new shader graph feature. Previously, I was using this shader, which worked great for awhile, but it ended up constantly breaking for seemingly no ...
0
votes
0answers
45 views

Check if Im following correctly a path

Hi Im developing a navigator app in android which trace a path to a destination node given a graph using Dijkstra algorithm. Now my problem is: How can I check if I have crossed a determind node in ...
4
votes
1answer
596 views

Procedurally generating dungeons using predefined rooms

Most attempts at procedurally generating dungeons I have stumbled upon do space out areas that will be rooms and connect them will corridors and hallways but what about instances where you have a ...
2
votes
0answers
95 views

Procedurally generated paths with intersections

The Problem I've been attempting to create some procedurally generated paths for a while now, but I've reached a problem when it comes to generating the intersections of the paths. The paths are ...
3
votes
2answers
151 views

What algorithm can I use to distribute energy between connected nodes?

I'm creating a game where every user has a network of connected nodes that each have a specific amount of energy. The nodes will try to distribute energy evenly amongst themselves. If a node has more ...
4
votes
1answer
133 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
260 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: ...
3
votes
1answer
106 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
153 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
64 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: ...
2
votes
1answer
195 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
811 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
157 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 ...
6
votes
3answers
283 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
596 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
83 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
1k 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: ...
6
votes
4answers
172 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
604 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
91 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
241 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
206 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 (...
31
votes
6answers
18k 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
385 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
126 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 ...
1
vote
1answer
214 views

Electronic circuit simulator four-way flood-filling issues

I've made an electronic circuit board simulator which has simply 3 types of tiles: wires, power sources, and inverters. Wires connect to anything they touch, other than the sides of inverters; ...
4
votes
2answers
314 views

How would I go about updating my electronic circuit simulator's 'electricity'?

I have made an application which allows the user to place down wires, power sources, and inverters on a virtual circuit board. All connections between tiles are automatic, as shown here: As you can ...
9
votes
3answers
3k 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
243 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
48 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
85 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
162 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
792 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
404 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
272 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 ...
6
votes
1answer
732 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
244 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
183 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....