Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

183 Neutral

About Tereth

  • Rank
  1. Tereth

    Delaunay Traingulation

      Nothing, I couldn't figure out how to implement it.  I'm sure it works, but all of the documentation/pseudo-code was over my head.
  2. Tereth

    Delaunay Traingulation

    Yeah so, after about 30 hours of trying to figure this out, I have thrown in the towel.  I've decided to use Hexagons, which have the properties of Voronoi Polygons, so functionally this is fine.  Perhaps, though, hexagons are not at attractive.  Here's what I've got so far.     Sorry, I don't know how to edit the title, but I would say this problem has been forgone, not exactly solved haha
  3. Tereth

    Delaunay Traingulation

    Ok so I see what I did wrong with the previous bit of code.  I wasn't making triangles with each edges and every other point. I tried this and the only problem is that it degrades at higher numbers of points.  It doesn't even look like the same program...  What could be going wrong?   So now here's what I did: -Made Every Edge Possible -For Each Edge, Make A Triangle  +If that triangle's circumcircle doesn't contain any other points then add that to the list of triangles  
  4. Tereth

    Delaunay Traingulation

        I feel like I am getting close!  I am getting some funky spaces in the middle of bunches of triangles though.  What do you think is causing this?     Here's the code I am using to solve for edges [my apologies ahead of time for lack of elegance]:   //Make Edges for(int a=0;a<pA.size();a++) {for(int b=a+1;b<pA.size();b++){ eA.add(new Edge(pA.get(a),pA.get(b))); }}   //Cull Edges ArrayList<Edge> cull = new ArrayList<Edge>(); for(int e=0;e<eA.size();e++) {for(int p =0;p<pA.size();p++){ if(!eA.get(e).remove&&eA.get(e).center.getDistanceSquare(pA.get(p))<eA.get(e).radiusSquare){ eA.get(e).remove=true; cull.add(eA.get(e)); }}}   for(int c=0;c<cull.size();c++) {eA.remove(cull.get(c)); }
  5. Tereth

    Delaunay Traingulation

      Ok, I took a swing at this and got pure chaos.  After about 5 points it really starts to go down hill.   Here's what I did: Made All Possible Edges Between All Points Made All Possible Unique Triangles Out of These Points    -In the Constructor of the Triangle Object I Solve for Circumcenter and Radius Cull Out All Triangles* That Had a non-Triangle* Point Within the Circumecircle   Here's what I got [4 Points Left; 5 Points Middle; 6 Points Right: Red Dots Are Edge Midpoints and Green Circles are the Circumcircles]:
  6. Tereth

    Delaunay Traingulation

      Do you have an example I could see?     This is a great link!  Thank you so much!  I'm not quite sure how this works though, because I don't understand the data types that are being used.  I'm using edges and vertices as well.   How is this solving for the edges?   I would greatly appreciate it if I could take a look at how you solved this!
  7. Tereth

    Delaunay Traingulation

      I've actually read through this text and found that the technical language is over my head.  As well, it doesn't provide step by step solutions to the problems, but rather general descriptions.  I'm sure these descriptions are the only road map an experienced programmer with a formal education in upper-lever math would need.  But I'm entirely self taught, so the nomenclature kills me.     This makes 100% sense.  I got it!  I also solved the whole Point within a triangle business, but found that clicks out side of the triangle are much harder to handle!  Right now I make a traingle with triangle edge with the nearest bisecting point.  This works for the first few, but falls apart.  I'm not sure how to solve for clicks outside of the trianlge.  
  8. Tereth

    Delaunay Traingulation

      I'm not quite sure what you're trying to say.  I'm looking to make a Voronoi type mesh because they have properties that not only make a great map from world gen, but also assist in higher order map problem solving.  Random poly's isn't exactly what I'm looking for.  I appreciate the response :)
  9. Tereth

    Delaunay Traingulation

        I actually came to this realization after working on this problem a few more hours!  I also see that my title is inaccurate/misleading.  My apologies.  I want to make a Delaunay Triangulation so that I can make a Voronoi Diagram.   Now I'm struggling to produce a Delaunay Traingulation.  I'm trying to make my initial set of triangles by adding points randomly to the grid.  If the point is inside of the triangle, then the triangle splits into three smaller triangles.  If it is outside of another triangle then it finds the two nearest points and makes a new triangle with them.   This is not working at all.  I don't understand Barycentric Coordinates, so I opted for a summation of internal areas with the new Point compared to the total area of the triangle.  This fails miserably, however the math my be wrong.   I'm using Area(Triangle) = |p1X*(p2Y-p3Y)+p2X(p3Y-p1Y)+p3X(p1Y-p2Y)|/2   Is there a better way to make a field of Triangles?   I've seen this concept of edge flipping in my travels.  I haven't been able to wrap my head around it well enough to turn it into code. Do you have a simplish explanation for what is going on?
  10. Tereth

    Delaunay Traingulation

    I'm using a Voronoi Diagram for map generation, but the way I came to my Voronoi Diagram is incredibly dirty; I solved for the pixels within the polygons and not actually the vertices of the polygons.  I then solve the vertices backwards.  This takes an eon and occasionally fails to solve for vertices and adjacent polygons.   I've looked at tutorials and explanations regarding Voronoi diagrams and Delaunay Triangulation and I understand how they work and I can draw them out on graph paper, but I'm having trouble putting these into an algorithm that produces a proper Voronoi Diagram.  Obviously, this has been done before, but all of the tutorials I've found skip steps.   I'll write out what my thoughts are so far and questions regarding each part.  Please let me know where my logic falls short or if you know an answer to my question.   Set -> n random points on a dSizeX x dSizeY grid   My thoughts on a solution: -For each point (Pn) find all other points with that have non-crossing lines to (Pn)    +The only solution I had for this was to make a line to all other points and cull out all that cross, keeping the lines that have closer points to Pn.  This seems like an incredibly inefficient way to do this.  Is there a better solution? -Find the bisecting perpendicular line to all lines left over [I've got this] -Find the intersections between all bisecting perpendicular lines to solve for Voronoi Vertices of the polygon. [I've got this]   If you have any comments, suggestions or links to tutorials that you think would be helpful, I would greatly appreciate it.  Also, if there's a simpler solution, I would be grateful for direction.   Thank you!   Here's a screenshot of my dirty diagram where I colored all polygons random colors:
  11. Tereth

    Town Generation

    @Ryutenchi: I appreciate the response and the idea.  That's a lot of what I have seen in my search.  I was looking for more complex city types.I'm basically looking for a modular city/town planning algorithm that can express the different cultures of the game just by adjusting the parameters.  In fact, most of my game works off of the same principle for dungeon generation, character generation and biome creation, however, making a city/town, I have found is very tricky.  For example, I want to make a tribal faction's cities look disorganized, but yet in clusters of families.  Whereas, I want more civilized factions to have cities that are more organized, with zoning and must more of the grid-like organization.  As well, much of the towns encountered are not huge metropolises, but rather hamlets of ranging from 10-50 people and I would like to have each one, even if they are apart of the same faction, look and feel like a unique settlement.   @Alvaro   This is such a cool idea!  I wish I could give you 20 thumbs up!  I could definitely use something like this for larger towns.  For the past few hours, I have been trying to see if I can use graph theory to build a minimum spanning tree between nodes in the city to develop the central paths of the town and then radiate paths from the central tree for peripheral homes.  The nodes being key points in the town's economy (i.e. farms, mine, place of government), which I would place according the the culture/economic focus of the town.  Let's see if this works out.   I may PM you at a later time about the referenced idea, if you don't mind.  I really appreciate your response!   Also, I am still open to more ideas!
  12. I am having trouble making a suitable Town Generating Algorithm.  I'm making a dungeon crawler/survival game in which the player encounters towns along their journey that are built on the pseudo-randomly generated maps.  It get's pretty boring when every town has the same basic pattern as well, it doesn't reflect the different cultures in the game.  I've looked at some materials on random town generation and I've been extremely underwhelmed.  That's probably because I don't know where to look.  Can anyone point me to some good resources or have any advice on this topic?
  13. I figured it out:   The final pathing correction would always work the first time.  Ends up there was in error in a previous pathing step that would not work if the distance between the center of the tile and the character's position wasn't divisible by the unit speed of the character.  So, even though the final correction wasn't being accessed at the time of the pathing freeze, it changed the parameters of earlier, erroneous, pathing logic for the next path resulting in a pathing freeze.   Wow...lesson learned: do not make the assumption that old logic will fit the parameters of new logic when debugging.   I don't know how to delete my own topic, but this is case closed.  Sorry everyone!
  14. [I am unsure as to if this is the best place to put this, please redirect to the proper place if I am incorrect]   In order to properly describe the bug, I must explain the order of events leading up to the bug:   1) Player Left Clicks Character to Move Character to the Active Character Handle [works] 2) Player Right Clicks to Set the Destination of Character in the Active Character Handle to the Point of Click [works] 3) Alpha* Pathfinding Ensues to Produce a Path of Tiles to the Target Location [works] 4) Character Follows Pathing Instructions to the Edge of the Final Tile [works] **Note: The Character Enters the Final Tile When it Meets the Edge of the Final Tile**   Now, if I add in a final step to correct the character's position within the final tile to reflect the mouse click, something strange happens.  Periodically, the pathfinding will work properly, yet, the Character will stop following pathing instructions after passing through a single tile and freeze until I give it a new path.  Even more strange, the new "final step" is in no way accessed during the steps (i.e. if I put a reporter method within the new code, I get no output from the reporter when the character freezes mid-path.)  If I then take the code out, the pathing works without a hiccup except for the fact that the character position is not corrected to the point in the tile that was clicked.  There are no freezes in the pathing without the corrective code...which is to my knowledge not accessed when the pathing freezes!   I have tried for hours to fix this problem, however, I cannot find a way around it.   Any insight into how to further debug this problem would be a phenomenal and welcomed helped.  As well, if there is something I am not considering please let me know.   If you would like me to post my code just let me know.  I am programming in Java in Eclipse.  
  15. I do remember reading that, however, I don't think i understood what I was reading, so I didn't make the connection. I'll go back through the FAQ again now that I have better understanding of what I am looking for. Thank you!
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!