Tagged: algorithm Toggle Comment Threads | Keyboard Shortcuts

  • frankiezafe 11:57 on 2017-04-15 Permalink | Reply
    Tags: algorithm, , , ,   

    My website being back online, I will document the researches related to disrupted cities in several pages there.

    I’m currently working on an algorithm to nicely shrink the blocks detected in the network…

     
  • frankiezafe 16:33 on 2017-03-26 Permalink | Reply
    Tags: algorithm, code, ,   

    Finding the closest road on the right at a crossroad.

    To generate the bocks of building based on the roads structure, the method I’m building is based on a simple idea: when you arrives at a crossroad, you take the first street on the right and you go on like this until you reach a dead-end or your starting point. If you reach your starting point, the succession of roads you took defines a block of building. In theory. This technique has been suggested by Michel Cleempoel, on the way back from school.

    After a bit of preparation of the road network (removing orphan roads, having no connection with others, and dead-ends parts of the roads), the real problem arouse: how do you define right in a 3d environment, without an absolute ground reference. Indeed, I can configure the generator to use the Y axis (top axis in ogre3d) in addition to X & Z.

    At a crossroad, you may have several possibilities of roads. In the research, these possible roads are reduced to 3d vectors, all starting at world’s origin. The goal is to find the closest vector on the right of the current one, called the main 3d vector in the graphic above..

    The right is a complex idea, because it induces an idea of rotation. The closest on the right doesn’t mean the most perpendicular road on the right side. Let say I have 4 roads to choose from. Two going nearly in the opposite direction of the road i’m on, one perpendicular and one going straight on.

    If I compute the angles these roads have with the current one, results are:

    1. 5°,
    2. -5°,
    3. 90°,
    4. and 170°.

    The winner is not the 90°, but the 5° road! If I sort them, the last one must be the -5°, who is the first on the left.

    3d plane from a 3d vector

    The first thing to do is to define reference plane. To do so, you get the normal vector of the road by doing a cross product with the UP axis (Y axis in this case). The normal gives you a second vector, perpendicular to the road, and therefore defines a plane. Let’s call it VT plane, for Vector-Normal plane. For calculation, we need the vector perpendicular to this plane, rendered by crossing the road and its normal, let’s call it the tangent vector. Until here, it’s basic 3d geometry.

    projection of 3d vectors on a plane

    We can now project all the possible roads on the VT plane. These are the yellow vectors in the graphic. The math are clearly explained tmpearce on stackoverflow. Implemented in processing, it gives:

          float d = othervector.dot( tangent );
          PVector projectedvector = new PVector();
          projectedvector.add( tangent );
          projectedvector.mult( d * -1 );
          projectedvector.add( othervector );
    

    We are nearly done!

    angle between 3d vectors

    The projected vectors will help the angle calculation. Indeed, the current vector and the projected ones being coplanar, they share the same normal. The way to get the angle between 2 coplanar vectors is described by Dr. Martin von Gagern, on stackoverflow, once again. See Plane embedded in 3D paragraph for the code i’ve used.

    And… tadaaammmm! The number rendered by the method is the angle i was searching for, displayed in degrees in the graphic above.

     
  • frankiezafe 18:58 on 2017-03-23 Permalink | Reply
    Tags: algorithm, , , gif, ,   

    Road network generation: the gif gives you an idea of the procedure executed in ~300 milliseconds by the c++.

    With a deformation:

     
  • frankiezafe 21:35 on 2017-03-19 Permalink | Reply
    Tags: algorithm, configuration, , network,   

    Different kind of network generated by 3 configurations (images go 2 by 2).

    Note: add a variation on the roads length (min, max will be ok).

     
  • frankiezafe 20:50 on 2017-03-18 Permalink | Reply
    Tags: algorithm, , ,   

    Result of different configuration of network at each pass. In each image, you see the road network alone and the network with the control grid. I’m proud to mention that the generation time on a big network is taking around 500 millis, something easy to hide with a small transition.

    Here, there are 3 + an initial road (the thick one). In each pass, the road becomes smaller and thinner.

    It’s also possible to generate the same network with depth enabled. It’s becoming very complex to follow visually, but it makes no mistake 🙂

     
  • frankiezafe 20:34 on 2017-03-11 Permalink | Reply
    Tags: algorithm, , , , ,   

    flat network (no Z)

    slight Z curvature

    strong Z curvature

    strong Z curvature

    strong Z curvature

    After a bit of struggle with the management of a 3d grid, the advantage is there: it’s now easy to generate a road network in 3D, with automatic connection of the streets while generating them. It’s a simple brute force & unsupervised generation algorithm, but it is memory efficient and error less.

    Just to explain a bit the images above: the cubes are the cells of the road grid. Only the required one are created during road generation. There are connected to each other to speed up the proximity tests once a now road segment is added. I’ll measure the generation time soon, but it’s already quite fast regarding to the first test made several days ago in processing.

     
  • frankiezafe 17:45 on 2017-03-11 Permalink | Reply
    Tags: algorithm, , ,   

    Generation of a 3d grid of cells, each one of the cells knows who are the surrounding ones. This to speed up searching around the current cell.

    To generate a unique id for each one of the surrounding cell, and quickly find the current cell in the surrounding cell, i used a python that generates a list of enum and a map of opposition. Therefore, when I create a new cell in the grid, its very fast to register it into all the existing ones.

     
  • frankiezafe 23:39 on 2016-12-16 Permalink | Reply
    Tags: algorithm, , , ,   

    Looking for loops in networks.

    It’s seems very simple, but when i’ve started to search for a programmatic way to solve this, you ends up with a kind of complexity that seems much too high compared to the problem.

    After a bit of research, i found the Rocha Thatte method. It is a very elegant way to detect “cycles” in “directed graphs”. Description in wikipedia.

    This is a js implementation, based on the java version, used to study the implementation.

     
  • frankiezafe 21:29 on 2016-11-16 Permalink | Reply
    Tags: algorithm, , ,   

    Finding cycles in networks.

    graph_cycle

    Since several days, i was trying to solve a problem that will occur in #peel: how to broke a connection when the connection is part of a “cycle” (i’ve called it “loop” until now). This problem is illustrated here:
    overall-structure-20160930-liberties-002-text

    The beginning of the answer is in wikipedia and uses graph theory >> https://en.wikipedia.org/wiki/Cycle_(graph_theory)

    Can’t wait to start coding that 🙂

     
  • frankiezafe 17:49 on 2016-08-30 Permalink | Reply
    Tags: algorithm, , ,   

    Puzzle research for peel.

    In the process of searching a “why” 1, the idea of a messed up structure to reconstruct arose. As the other concepts in the game, it’s easy to understand visually, a bit more hard to describe programmatically. Indeed, once several segments will be connected, rotations will be constrained, and hierarchy tree (3d objects parenting) has to be rebuild.

    In these images, the player starts in the left state, and after rotating and connecting all the parts, he/she ends up in the right state. The images show something looking like a level, but i’m planning to add dynamically the next segments to generate the sensation of an endless puzzle.

    The puzzle starts at the bottom.

    overall-structure-20160930-002

    overall-structure-20160930-001

    Axis of liberty: each start joint (in fuschia) has 1 degree of freedom.

    overall-structure-20160930-liberties-001

    Note: cluster (orange wireframe cubes) must be attached to connector or gap (for the 2 first ). Each cluster knows wich joints are presents in it. If a segment moves, the joints move with it, and potentially reach the next cluster.

    By building a slightly more complex structure and trying out joint rotation with connected segments, collision issues starts to show up!

    overall-structure-20160930-liberties-002-text

    First try could be solved by shortenning a bit the segments:

    overall-structure-20160930-liberties-003

    But these issues can not be quickly fixed:

    overall-structure-20160930-liberties-004

    overall-structure-20160930-liberties-005

    overall-structure-20160930-liberties-006

    Enabling and disabling liberties is a crucial point in game mechanics, and will not be easy to calculate… At least, i don’t have the solution popping out right now.

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel