# Questions tagged [graph]

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

57 questions
Filter by
Sorted by
Tagged with
266 views

### Line of Sight Check Theta* Algorithm

I am looking at implementing the Theta* algorithm in a 2D NavMesh. I have A* working, and I need to add a line of sight check to turn it into Theta*, this seems relatively easy in a uniform grid but a ...
3k views

### Efficient Algorithm for the boundary of a set of tiles

I have a grid of tiles of a known finite size that forms a map. Some of the tiles inside the map are put into a set known as a territory. This territory is connected, but nothing is known about its ...
27 views

### Unity - Shader Graph not displaying preview in HDRP

I'm working on a new project (Unity 2019.2.4f1, HDRP). I made my first PBR shader and it works correctly when applied to a material, but it doesn't display anything on the Main Preview in the Shader ...
64 views

### Snake AI - Is a Hamiltonian approach valid for all grid sizes?

So, as has been done many times before, I am designing an AI that can play Snake as effectively as possible. It didn't take me long to find this extremely useful thread here: How to find a safe path ...
222 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 ...
2k 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: ...
312 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 ...
256 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 ...
115 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 ...
327 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: ...
257 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 ...
503 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 ...
21k 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 ...
923 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 ...
323 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 ...
220 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; ...
967 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-...
133 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 ...
9k 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 ...
170 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 ...
4k 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 ...
165 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 ...
286 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 ...
88 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 ...
244 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 ...
197 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. ...
141 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. ...
71 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: ...
739 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,...
223 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 ...
175 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 ...
728 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 ...
95 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 ...
265 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 ...
245 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 ...
426 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....
2k 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 (...
120 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 ...
135 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 ...
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 ...
49 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.
87 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 ...
196 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 ...
854 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-...
418 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 ...
3k 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 ...
277 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 ...
2k 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 ....