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
51
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,048
0
votes
0
answers
54
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
84
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 ...
- 111
1
vote
0
answers
86
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
47
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
846
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
504
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
285
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
91
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
9k
views
How does HPA*(Hierarchical Pathfinding A*) really work?
I'm currently researching for a summary paper on the different variants of A* search algorithm and how they are used in games and I stumbled across the name HPA*. I've heard that it's much more faster ...
4
votes
1
answer
1k
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
330
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
81
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
1
vote
1
answer
1k
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 ...
- 11
2
votes
1
answer
543
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
823
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
1k
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
196
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
870
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
776
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 ...
- 808
3
votes
2
answers
302
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
240
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
226
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
306
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
78
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.5k
2
votes
1
answer
392
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,907
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
698
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
314
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,907
0
votes
1
answer
106
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
201
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.5k
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
105
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 ...
- 363
1
vote
1
answer
384
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
352
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 ...
- 957
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 (...
- 614
51
votes
7
answers
35k
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 ...
- 621
2
votes
1
answer
652
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
141
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
183
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
260
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
387
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
6k
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
331
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
54
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