Questions tagged [graph]
A graph is a data structure for a set of objects where some pairs of the objects are connected by links.
69 questions
0
votes
0
answers
80
views
How to optimally transfer between nodes when each connection can only handle a certain number of things at a time?
Let's begin with a picture:
I am currently making a turn-based strategy game set in space where you can settle colonies and have to transfer minerals from the colonies ("foo", "bar&...
- 8,543
0
votes
0
answers
207
views
Unity shader graph show through walls
How to make a shader graph shader display through walls while keeping the existing texture in unity. I also only want to use shader graph only nothing else.
Example: https://hyunkell.com/blogfiles/...
- 1
0
votes
1
answer
214
views
How to compile a node-based material system to usable shader code / data buffers / texture resources?
Let's suppose we're rendering a scene using Vulkan with objects with many different materials that are built using nodes.
Within a graphics pipeline, there can be only fixed shader code, so I'll have ...
- 113
1
vote
0
answers
221
views
Dynamically generating the layout of a skill tree
How would I go about automatically generating the layout of a skill tree?
Skill tree nodes have at least one parent, but they can have more. Ideally I'd have a root node that recursively creates its ...
- 11
1
vote
0
answers
57
views
Pushing Multiple Objects With Static Friction
Given is a set of objects at rest that are in contact with each other, external forces that are applied to them and static friction forces (forces that counteract an applied forces up to a maximum ...
- 11
2
votes
1
answer
1k
views
Issue with Goal Oriented Action Planning (GOAP) and multiple preconditions
So I am working on an AI for my game using GOAP. I've been researching it for the past few days and while implementing it on my own I've ran into a problem. Here is a diagram of what I am doing.
The ...
- 21
0
votes
0
answers
570
views
Gradient border/drop shadow URP unity shader graph
I am using Unity Universal Render Pipeline and shader graphs in my game. Does anybody know how I would go about setting up a shader graph that adds a black gradient drop shadow/border with the game ...
- 1
3
votes
1
answer
339
views
How are GraphNode String IDs supposed to be used
Once you add several GraphNode instances to GraphEdit they get some unusual ID strings surrounded with ...
- 133
0
votes
0
answers
125
views
Graph structure/algorithm to maintain an incrementally updated component list
I have a c# unity game (using quikGraph, but I don't believe it fits my needs here).
I'm adding wires which connect power sources to power destinations.
All devices and wires will be nodes in a graph.
...
- 143
2
votes
2
answers
12k
views
How does HPA*(Hierarchical Pathfinding A*) really work?
I'm currently researching, for a summary paper, the different variants of A* search algorithm and how they are used in games.
I stumbled across the name HPA*. I've heard that it's much faster than ...
4
votes
1
answer
2k
views
space map generation
I am at the beginning of the creation of a space 4x and first of all i need to generate a galaxy of stars linked by connecting lines that changes in each new game, I'll add a few pictures to show what ...
- 41
1
vote
0
answers
377
views
Generate road mesh from a graph
I want to generate a mesh for the entire road network(later I'll probably want to split it into chunks but for now this will do).
My road network is stored as a ...
- 21
0
votes
0
answers
95
views
How do I get HDRP render enabled so that the shader graph will work
I'm using Unity 2019.2.17 personal, and I imported the shader graph package and created a pbr shader graph. I get a warning: the render pipeline is not compatible with the master node. I assume it ...
- 510
13
votes
6
answers
5k
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 ...
- 318
2
votes
2
answers
2k
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 ...
- 21
2
votes
1
answer
1k
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 ...
- 23
6
votes
1
answer
878
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 ...
- 245
0
votes
2
answers
1k
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 ...
- 179
1
vote
2
answers
2k
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:
...
- 13
1
vote
2
answers
240
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 ...
- 111
1
vote
0
answers
889
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 ...
- 11
3
votes
1
answer
3k
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 ...
6
votes
0
answers
837
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 ...
- 838
3
votes
2
answers
368
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 ...
- 213
4
votes
1
answer
292
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 ...
- 247
2
votes
1
answer
272
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.
...
- 125
1
vote
1
answer
343
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.
...
- 19
4
votes
1
answer
102
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:
...
- 10.6k
2
votes
1
answer
453
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 ...
- 4,927
3
votes
1
answer
2k
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
1
answer
785
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 ...
- 295
6
votes
3
answers
357
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
1
answer
1k
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,...
- 4,927
0
votes
1
answer
128
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 ...
- 1
9
votes
2
answers
4k
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:
...
- 203
6
votes
4
answers
262
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 ...
- 10.6k
1
vote
2
answers
1k
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 ...
- 33
0
votes
0
answers
118
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 ...
- 373
1
vote
1
answer
417
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 ...
- 244
2
votes
1
answer
388
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 ...
- 967
7
votes
3
answers
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 (...
- 634
52
votes
7
answers
37k
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 ...
- 631
2
votes
1
answer
716
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....
- 121
1
vote
1
answer
163
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 ...
- 147
0
votes
1
answer
201
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 ...
- 147
1
vote
1
answer
286
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; ...
- 113
4
votes
2
answers
456
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 ...
- 113
10
votes
3
answers
7k
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 ...
- 201
2
votes
2
answers
376
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 ...
- 121
0
votes
0
answers
57
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.
- 178