# I spy a diagram

3 replies to this topic

### #1 Rani_sputnik

Rani_sputnik

GMC Member

• GMC Member
• 437 posts
• Version:GM:Studio

Posted 01 November 2011 - 03:33 AM

Spoiler

Does anyone know what this diagram is called? It's a way of partitioning space in a way similar to a voronoi diagram except that it only uses rectangles. I want to do some research but I don't know what to search...
Also if anyone has tried implementing one it would be even more fantastic if you could give me some hints, but a name will suffice :D

EDIT: MY tutor thought I was talking about quadtrees, similar but no.

EDIT2:

I've had an idea for the algorithm that I also want to run by people. This is what it consists of

```
with obj_particles // With all the dots
{
build_rectangle(x-d,y-d,x+d,y+d); // build a square around the particle
resolve_any_particles_close(d); // d defines 'close together'
}

with obj_corners // With all the corners of these squares
{
i = find_shortest_distance_to_intersection();
build_line(x,y,  i.x,i.y);
}

```

I think that would solve it but I'm wondering how to make the find_shortest_distance_to_intersection fast?
I might build two lists that contain all the lines from both left to right and top to bottom. That way the algorithm can just work its way up/down the list.
What do you guys think? Is there something that isn't clear (it feels like a lot of this is just me ranting), can you think of a scenario that would break the algorithm? (It feels really naive) Any help is appreciated.

Edited by Rani_sputnik, 01 November 2011 - 07:53 AM.

• 0

My games - Boy Goes to Space, Proleague (Facebook & Kongregate), Making WayJam Tart (GMCJam#14) and Seal Fighter

Currently working on FloxGM - All-in-one backend for leaderboards, scores, cross device saves and analytics

### #2 Agamer

Agamer

GMC Member

• GMC Member
• 155 posts

Posted 09 April 2012 - 06:27 PM

I know you probably don't care for my response since you posted this a year ago.

I know it's not exactly the same since they're squares, but I hope it helps. A quadtree is basically a method of fractioning cells such that points in a plane are separated into individual squares.

EDIT: of course, you do specify it's not a quadtree, so... ?

I really can't figure out what you're trying to say. What do you mean find_shortest_distance_to_intersection?

Edited by Agamer, 09 April 2012 - 06:35 PM.

• 0

Package designer; resource maker; engine builder; program tool creator -- Be fully prepared to game:

My scripts My images My model designer My GUI components One of my engines Accepting texture requests

### #3 Yal

Yal

Not Tsuka

• Global Moderators
• 10151 posts
• Version:GM:Studio

Posted 23 April 2012 - 11:25 AM

I've PM:ed Rani, since his last activity was yesterday he's still active on this forum.
• 0

- The above is my personal opinion and in no way representative of Yoyogames or the GMC, except when explicitly stated -

Open this spoiler for my games:

Spoiler

Some useful game engines: (all completely free to use, even commercially, as long as you replace all included graphics / music first).
SisterEngine RPG Engine - - YaruFPS 3D Collision Engine -- YaruPlatEngine Platform Engine

New user? Can't draw but want to look unique? You can request a new avatar in this thread!

### #4 Rani_sputnik

Rani_sputnik

GMC Member

• GMC Member
• 437 posts
• Version:GM:Studio

Posted 24 April 2012 - 12:11 PM

Hey Agamer.

I ended up giving on this because it didn't end up being so efficient (and I still don't know what it's called), but in case you are interested I'll explain what it was. I can't remember what I was going to use it for but basically I wanted to divide up space into a bunch of rectangles defined by a set of random points. Here's a step by step of what I thought it would do.

> The 'diagram' takes in a set of random points.
> Each point builds a box of a set size around it.
> This leaves the remainder of the space as an odd shape around the points.
> I found if every square corner had 3 lines connected to them that ensured that the entire grid was divided into rectangles.
> So for every corner with 2 lines joined we add another line that extends out until it meets a line that crosses it's path -> note that this is what I originally had as find_shortest_distance_to_intersection().

Hopefully that clears it up a bit. Are you interested in the diagram too? Or was this just trying to help me out given the severe lack of replies hehe

And thanks for the pm Yal! Mucho Cudos
• 0

My games - Boy Goes to Space, Proleague (Facebook & Kongregate), Making WayJam Tart (GMCJam#14) and Seal Fighter

Currently working on FloxGM - All-in-one backend for leaderboards, scores, cross device saves and analytics