GDR Forum Index
Podcast Podcast
Dev Dev Logs
Search Search
RSS RSS
Register Register
Log in Log in
Reply to topic GDR Forum Index -> Game Developer's Refuge -> Development Log - Kingmaker Page Previous  1, 2
View previous topic :: View next topic  
Author Message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Thu Feb 02, 2012 2:24 pm    Post subject: Reply with quote

Yeah, I thought of something similar where I start with a map of squares and then do some midpoint displacement on the edges. Perhaps removing a few edges here and there randomly. No idea either if this would generate anything worthwile but might be worth investigating, shouldn't be too hard to do.

Another idea was to kinda fake a Voronoi diagram by using the random points as vertices, and then connecting each vertice to its three nearest neighbours. However, there must be some constriction on the minimum angle between the edges going from one vertice to its neighbours, as otherwise it would look weird. The hard part would be how to make sure that you end up with all cells closed, i.e. what if you are trying to find the last nearest neighbour for a vertice and you can't find one because it wouldn't satisfy the "two edges angle" criteria. You would end up stuck in a loop, unless we use a counter of some sorts to so we can give up and make due. There might be some strategy that would solve this, but I don't see it.

Thanks for the input though! And any other suggestions are very welcome!

I have found some nice information on the Bowyer-Watson algorithm for the Delauney triangulation and I'll try to make that work as my next order of business. For once an implementation that uses sane (read: noob-friendly) data structures. Quad-edges scare me. Heh, even though if this project would end up in nothing, I have certainly learnt a lot about computational geometry - by that I mean I know more stuff but not necessarily do I know much about them :)
View user's profile Send private message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Fri Feb 03, 2012 9:23 am    Post subject: Reply with quote

PROGRESS!!!



Hell yes. Next step is to get the voronoi diagram from this delaunay triangulation, which hopefully will be trivial.

My implementation is based on (or converted rather) from here: http://paulbourke.net/papers/triangulate/
It uses very sane data structures. A Point that holds xy-coordinates. An Edge that holds the index values to two Points. A Triangle that holds index values to three Points. That is all. No need to get fancy :)
View user's profile Send private message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Fri Feb 03, 2012 11:39 am    Post subject: Reply with quote

Yes, it was trivial. However, I still need to create the polygons. Right now I only have the points and edges of the voronoi diagram. I need the polygons so I can draw the voronoi cells in different colors and make them clickable.



View user's profile Send private message
PoV
Moderator

Joined: 21 Aug 2005
Posts: 10782
Location: Canadia
PostPosted: Fri Feb 03, 2012 11:48 am    Post subject: Reply with quote

Voronoi regions are all convex polygons, so a triangle fan from the "center" point should work.
_________________
Mike Kasprzak
'eh whatever. I used to make AAA and Indie games | Ludum Dare | Blog | Tweetar
View user's profile Send private message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Fri Feb 03, 2012 12:40 pm    Post subject: Reply with quote

But how do I find the surrounding voronoi vertices?

Hmm:

Code:

for each "center" point C
   for each triangle where C is a vertex
       store the triangle's circumcenter point (what I refer to as a voronoi vertex)


This way I can get all the points that should be in the polygon. Somehow I must ensure that they are added to the polygon or triangle fan in the right order though.

Perhaps not the most efficient way, but a convex hull algorithm might work. My implementation of Graham's scan was not in vain! :)

Thanks for the suggestion! Just what I needed to start thinking about the problem.
View user's profile Send private message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Sun Feb 05, 2012 12:41 pm    Post subject: Reply with quote

Ok, so the first little milestone is approaching. My goal is to restructure the code so it's nice and clean, so I don't have to think about that when it's time to actually implement the game logic. Next update will contain a release (mac only for a while) where a map is randomly generated, being rendered in a minimalistic fashion but hopefully in an aesthetically pleasing way, with populated provinces that are clickable. I'm hoping to include a fixed zoom-feature too which means the map has to be scrollable also. This might take a while though because life is getting in the way right now. But I have a reachable, set goal which is always a good thing. Until then!
View user's profile Send private message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Wed Feb 15, 2012 6:19 am    Post subject: Reply with quote

I lied, there won't be any release today, mostly because I'm too eager to show off some screen shots :)

I didn't really have to do a proper graham's scan, as, which was previously noted, the points making up the triangle fan are already convex and all points identified should be included in the fan anyway. I had some problems at first though:



But that was beacuse of a stupid mistake on my part. Took a while to figure it out though. Here's the voronoi cells in random blue colors:



I still need to make some proper borders, and then start to fill in the cells with land and whatnot.

On another note, I must say that just having this devlog and being able to update with whatever progress or problems I have is very motivating. So, thanks for this forum and all of you reading and commenting :)

The release might take a while, so there will be some updates with screenshots inbetween.
View user's profile Send private message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Thu Feb 16, 2012 1:23 pm    Post subject: Reply with quote

I took a risk and restructured my code a LOT, and it worked without too much hassle to my surprise. I can now generate lone islands. I shamelessly stole the generation code from amitp, but will have to tweak it probably a bunch to get what I need.

First, some art as an effect of failure:



Complex (for me at least) code makes for stupid mistakes. But hard work prevails! And the result...

View user's profile Send private message
Sirocco
Moderator

Joined: 19 Aug 2005
Posts: 9412
Location: Not Finland
PostPosted: Thu Feb 16, 2012 3:48 pm    Post subject: Reply with quote

Ah yes, the old "one vertex stuck at 0,0" error. I love seeing that in games... especially when it happens in Fallout 3 ^__^

That last screenshot looks very promising.
_________________
NoOP / Reyn Time -- The $ is screwing everyone these days. (0xDB)
View user's profile Send private message Visit poster's website
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Fri Feb 17, 2012 4:49 pm    Post subject: Reply with quote

Thanks!

I had to step back for a bit and sanitize my code a tad. Always fun to just code stuff to make things happen, but I got intro trouble trying to generate landmasses with varying elevation. I have now begun splitting up the monolithic Map class into subunits. The Delaunay part is done, and I implemented Poisson disk sampling (the most inefficient solution ever) which calculates a minimum distance between points depending on the size of the map and the number of points and then evenly distributes them. This way I don't have to do any lloyd's relaxation on the voronoi regions.
View user's profile Send private message
arvidsson
Contributor

Joined: 13 Jun 2011
Posts: 109
Location: Sweden
PostPosted: Fri Mar 16, 2012 7:38 am    Post subject: Reply with quote

A little update. My game has changed direction a bit - going from grand strategy to a bit more strategy/tactical kind of game. This means that I'll probably drop the voronoi map generation idea and go for regular hexagon tiles. A lot of work for nothing perhaps, but I might still end up using the algorithms for other projects and I did learn a lot. For me, one of the hardest things when creating games is to evaluate whether my ideas are creative enough. I tend to become inspired by other games a bit too much sometimes and end up feeling my ideas are essentially copycats. Looking at Crusader Kings II, that's basically what I wanted my game to become, albeit not historically bound nor as complex, but with more focus on the life in court. However, sometimes you are forced to realize that your ideas, albeit awesome, are too grand and too complex for a one-man project.

I have been playing some more tactical games and now I want to draw inspiration from those experiences into my game. So, I guess I could say the focus shifting from complex nobility relationship simulator to a more conventional board game. I know this is all pretty vague and that's because I'm not entirely sure myself of in what direction this is going exactly. My aim is a game that is built on simple concepts and as little randomness as possible, but where the combination of the simple concepts are easy to learn but hard to master - a bit like chess really. Making the game less random is worth striving for because I want the player to be able to create a grand strategy for himself and then execute it using tactical means. So it's more about adapting to what your opponent does than adapting to a horrible situation because you lost a key battle where success should have been certain.

I'll keep on working and what happens happens :)
View user's profile Send private message
Reply to topic GDR Forum Index -> Game Developer's Refuge -> Development Log - Kingmaker Page Previous  1, 2

Use this link to get a Sign-On Bonus when you get started!

All trademarks and copyrights on this page are owned by their respective owners. All comments owned by their respective posters.
phpBB code © 2001, 2005 phpBB Group. Other message board code © Kevin Reems.