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

learn more… | top users | synonyms

-3
votes
0answers
28 views

Game Development Company Database [on hold]

I'm doing a project which requires making an ER diagram for a game company. Could anyone think of attributes for: Quality Assurance Programmer Designer Development Team Publisher Genre Platform
5
votes
3answers
907 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 ...
18
votes
4answers
3k 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 ...
1
vote
1answer
92 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
81 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 ...
0
votes
0answers
48 views

Random Facebook Friends Profile Pictures

I'm thinking of a new game for iOS. It's a social game that needs a random image generator with the images of your Facebook friends. My first question is: is this even possible? My second question is: ...
2
votes
2answers
89 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
43 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
57 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
85 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
237 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 ...
5
votes
1answer
477 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
305 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 ...
2
votes
2answers
176 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
242 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
662 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 ...
1
vote
1answer
1k 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
125 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
140 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
1k 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 ...
5
votes
1answer
3k 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
174 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
305 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
738 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
546 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
2k 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
814 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 ...