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 - Mayas, floating islands, ... 'n' stuff
View previous topic :: View next topic  
Author Message
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Mon Oct 29, 2012 4:47 pm    Post subject: Development Log - Mayas, floating islands, ... 'n' stuff Reply with quote

Hi there!

I've been quiet on the forums recently, but just because I started working on my next project and didn't want to post about it until I had *something* to show.
It should become an RTS, with elements from dwarf fortress inside. Also, a lot of building... scaffoldings, houses, bridges, ... all that stuff! :D

Video time!

I'm basically just telling the peasants where to build stuff. Currently only bamboo fields and scaffoldings. They operate completely on their own. I'm currently trying to find a good algorithm for distributing the workers to the nearest work places at all times. Seems like a problem I will have to cram out my math skills for (especially graph theory, from what I've read so far). If somebody of you knows anything about it or can give me some advice, I'd be glad! To describe the problem more sophistically: at each time, I have M workers that want to work (have nothing to do, are idle). I also have N available jobs at certain positions in the level. I would like to distribute the M workers on the N jobs so that the path lengths of the workers to the jobs are minimal. Some workers might not even be able to reach some jobs. In general, M!=N.

Bamboo can be harvested (and in the video is returned by the peasants to some invisible storage places). Scaffoldings are one of the major means of reaching new places and making stuff accessible. Want to get to the other side of a canyon? Build scaffoldings!
I want fertile soil to be a resource in itself in the final game. If you build houses on solid ground, you loose valuable space for planting stuff (like bamboo). It's much better to build scaffoldings above the ground and place the houses there. The shown map doesn't really reflect the sparcity of space I want in the final game.

And yes, graphics are abysmal! ;)
View user's profile Send private message Visit poster's website
Alex
Developer

Joined: 05 Sep 2005
Posts: 1159

PostPosted: Mon Oct 29, 2012 7:35 pm    Post subject: Reply with quote

I'm imagining King Kong busting through it.
looks cool so far!
View user's profile Send private message Visit poster's website
Sirocco
Moderator

Joined: 19 Aug 2005
Posts: 9330
Location: Not Finland
PostPosted: Tue Oct 30, 2012 5:11 pm    Post subject: Reply with quote

Reminds me of Lemmings, with the little guys running over the green landscape.

You can set up nodes along your map, then use A* to figure out how far away each guy is from a goal; this also gives you their travel time, and whether or not they can reach it. Then you'll have to weigh the available jobs against your work force, and divvy out the tasks.
_________________
NoOP / Reyn Time -- The $ is screwing everyone these days. (0xDB)
View user's profile Send private message Visit poster's website
Gil
Developer

Joined: 14 Nov 2005
Posts: 2341
Location: Belgium
PostPosted: Wed Oct 31, 2012 12:29 am    Post subject: Reply with quote

There's a whole branch of science dedicated to this problem and I followed a course on it in college, I just forgot what it's called :/
_________________
PoV: I had to wear pants today. Fo shame!
View user's profile Send private message Visit poster's website
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Wed Oct 31, 2012 12:34 am    Post subject: Reply with quote

Sirocco wrote:
You can set up nodes along your map, then use A* to figure out how far away each guy is from a goal; this also gives you their travel time, and whether or not they can reach it. Then you'll have to weigh the available jobs against your work force, and divvy out the tasks.

That's what's happening in the video already. For each job, the worker with the shortest path is assigned. The problem is that this doesn't always produce the optimal solution. Sometimes, workers need to travel more than they should... It's a greedy algorithm so the order in which the jobs are checked matters.
I learned that it's a linear optimization problem and i might need to implement a more sophisticated algorithm to solve this correctly... or i might be able to fake a good enough solution with some heuristics... or just brute-force my way to victory! :D
View user's profile Send private message Visit poster's website
Gil
Developer

Joined: 14 Nov 2005
Posts: 2341
Location: Belgium
PostPosted: Wed Oct 31, 2012 2:38 am    Post subject: Reply with quote

Linear programming! That's it. Yeah, I should be able to help you with that if you want.

I'll go look up what's needed. The algorithm isn't that complex really, if you know how to work it.

EDIT: The easiest one (and more than enough for your needs I assume) is the Simplex, which progressive interpolates IIRC, so I assume it's a recursive algorithm over a matrix.

Basically, linear programming problems solve a number of equations for an optimal X (eg, X needs to be as large as possible or as small as possible). In this case you want to optimize for total worker distance (or if you have a more complex metric for measuring efficiency, like a heuristic, use that).

I assume that worker distance for a certain worker to a certain point equals the A* path or whatever. Once you have the matrix all set-up with the correct values, the rest is just running it through Simplex recursively until you arrive at an optimal solution and go from there. The algorithm might be a bit taxing, in which case you could look into caching certain parts of it (I'm not sure if it's possible, but if three workers fight over the same job and one wins, you shouldn't redo that calculation if they haven't moved and are still in the job pool, stuff like that).

I hope that helps a bit, if you need help with Simplex, do ask
_________________
PoV: I had to wear pants today. Fo shame!
View user's profile Send private message Visit poster's website
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Wed Oct 31, 2012 10:34 am    Post subject: Reply with quote

Spot on, Gil! :) I drew exactly the same conclusions. And low and behold, I took a course at university this semester called "mathematic methods of visual computing" not knowing what to expect and we started to delve into exactly this topic this week. We came as far as defining the basic form of linear optimization problems (the matrix form). We'll start with the Simplex algorithm next week. One of the rare occasions where the stuff I learn at university is actually helpful! I'm only slightly worried because as I see it, it's a integer linear optimization problem, which *might* be more complicated... but I'll see...
So I'll postpone this topic until then... I've got thousands of other things on my todo-list anyway. :)

Should I fail (miserably) at implementing it, I'll gladly accept your help! TIA :)
_________________
My current project: Hook'd
View user's profile Send private message Visit poster's website
Sirocco
Moderator

Joined: 19 Aug 2005
Posts: 9330
Location: Not Finland
PostPosted: Wed Oct 31, 2012 1:48 pm    Post subject: Reply with quote

Also, be careful not to overthink this. The end user has almost zero chance to see a difference between a 100% mathematically perfect solution and a >90% good hack.

But if you have an opportunity to apply something you learned in class, go for it. I'm pretty sure I never have... heh.
_________________
NoOP / Reyn Time -- The $ is screwing everyone these days. (0xDB)
View user's profile Send private message Visit poster's website
Gil
Developer

Joined: 14 Nov 2005
Posts: 2341
Location: Belgium
PostPosted: Thu Nov 01, 2012 10:59 am    Post subject: Reply with quote

IMakeGames wrote:
Should I fail (miserably) at implementing it, I'll gladly accept your help! TIA :)

No problem, I'd be glad to
_________________
PoV: I had to wear pants today. Fo shame!
View user's profile Send private message Visit poster's website
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Tue Nov 06, 2012 4:40 am    Post subject: Reply with quote

Second WIP video:

Been working on the pathfinding stuff some more. I increased the pathnode-density to allow more precise movement and because the old system was a hackfest with different coordinate systems and strange helper classes called "DoubleNode". I also started implementing warriors. Unlike the workers (which sport a blue... tanga now), you control the warriors directly. The video shows this a bit, commanding warriors around the map. This is where the RTS component comes in. You can give warriors different weapons: spears, swords, bows,... To defend against other tribes and wild animals, you must place your warriors in strategically good positions. You can even build scaffoldings and tower-like structures for your archers so they can rain down arrows from above and are protected from melee units.
You can now place houses where the workers return their cut-down bamboo sticks to.
Also worked on the build-system some more. You can now build and unbuild stuff at any time. Building stuff still doesn't cost any resources though. :)
There are still some edge cases where things don't behave as I want them to. For example, when you remove the scaffold below a warrior, he becomes trapped (warriors can't climb scaffoldings).

Next, I want to implement the first enemy unit, which is just a wild animal you can hunt down for food. Did I mention you will need to gather food to survive? :D
View user's profile Send private message Visit poster's website
Gil
Developer

Joined: 14 Nov 2005
Posts: 2341
Location: Belgium
PostPosted: Tue Nov 06, 2012 7:26 am    Post subject: Reply with quote

I'm loving this so much :)

Can't wait for release.
_________________
PoV: I had to wear pants today. Fo shame!
View user's profile Send private message Visit poster's website
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Tue Nov 06, 2012 12:42 pm    Post subject: Reply with quote

Alright, I had my next lecture today... but, typical university, after 2 hours of definitions, lemmas, corollaries and theorems, I still don't know how the simplex algorithm works. Of course I could find out myself, but I feel like I can spend my time more efficiently when I'll learn about it in the lecture anyway. Untill next week, hopefully!

Thanks Gil, I can't wait either! ;)
_________________
My current project: Hook'd
View user's profile Send private message Visit poster's website
Sirocco
Moderator

Joined: 19 Aug 2005
Posts: 9330
Location: Not Finland
PostPosted: Tue Nov 06, 2012 3:27 pm    Post subject: Reply with quote

You've certainly got a good thing going on there. It has a nice, original visual flavor too.

This reminds me I need to shore up my existing projects so I can get back to the Dunjon game :|
_________________
NoOP / Reyn Time -- The $ is screwing everyone these days. (0xDB)
View user's profile Send private message Visit poster's website
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Sun Nov 11, 2012 2:28 pm    Post subject: Reply with quote

I've just finished implementing "hanging" ropes. It's the way to go if you want to go to a new area that's under you and you can't reach yet. You can't reach it with scaffolding alone as they need to be built from the ground up, while ropes are thrown downwards...

Left to do: bridges that allow your peasants to travel sideways between islands... I'm not sure yet how the mechanics on that should be, considering that your guys are normally on only one side/one island. Maybe when building a bridge, the peasant building it simply throws a hook attached to a rope to the other end, fixes the rope and works from there. Or I just let them build it from one side like it's magic! :D

Also did some UI improvements and minor changes to the construction/building system. For example, you can now not remove planks below buildings anymore (which would make the buildings hang in mid-air).
View user's profile Send private message Visit poster's website
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Sun Jan 27, 2013 5:12 am    Post subject: Reply with quote

Again, I've been pretty quiet here on the forums. But not because I've been slacking, but I've had many exams and also a ton of work to do ironing out many things concerning my game Rico.

But, I've also had some time to work on this game:

There are now two types of inhabitants in your town, workers and warriors. Warriors can use different weapons and attack enemies (like the boars) automatically. They can also be commanded directly.
You can now build buildings, like the bamboo storage house where the workers bring back their cargo.
Growing plants now drain the soil of energy, visible through the particle effects. The energy is slowly regenerating over time though. I plan on adding watering pipes you can build to nourish the soil consistently.
Fog of war is also rudimentarily implemented.

The violet stuff you see is a tumor that spreads across the ground. It is supposed to work similarly to creep in StarCraft 2, but I have a few different things in mind. It spreads and destroys any soil it touches and also makes building stuff impossible. So an important thing is not allowing the plague to spread.
View user's profile Send private message Visit poster's website
Alex
Developer

Joined: 05 Sep 2005
Posts: 1159

PostPosted: Sun Jan 27, 2013 9:29 am    Post subject: Reply with quote

video is set to private so can't watch it.
View user's profile Send private message Visit poster's website
IMakeGames
Contributor

Joined: 13 Apr 2011
Posts: 499
Location: Austria
PostPosted: Sun Jan 27, 2013 9:30 am    Post subject: Reply with quote

Alex Hanson-White wrote:
video is set to private so can't watch it.

Oh shoot! Should be fixed now :)
View user's profile Send private message Visit poster's website
Alex
Developer

Joined: 05 Sep 2005
Posts: 1159

PostPosted: Sun Jan 27, 2013 9:43 am    Post subject: Reply with quote

ah cool.. Looks like it's coming along. I like the arrows. They're slaughtering those animals. Do you plan to make the animals tougher and less frequent? I'm imagining like a group of them chasing an animal etc. at the moment the animal oesn't seem that tough.
View user's profile Send private message Visit poster's website
PoV
Moderator

Joined: 21 Aug 2005
Posts: 10584
Location: Canadia
PostPosted: Sun Jan 27, 2013 9:55 am    Post subject: Reply with quote

Looks neat, albeit dark.
_________________
Mike Kasprzak
'eh whatever. I used to make AAA and Indie games | Ludum Dare | Blog | Tweetar
View user's profile Send private message
Sirocco
Moderator

Joined: 19 Aug 2005
Posts: 9330
Location: Not Finland
PostPosted: Tue Jan 29, 2013 4:12 pm    Post subject: Reply with quote

It's this kind of lemmings meets warcraft vibe that intrigues me.
_________________
NoOP / Reyn Time -- The $ is screwing everyone these days. (0xDB)
View user's profile Send private message Visit poster's website
Reply to topic GDR Forum Index -> Game Developer's Refuge -> Development Log - Mayas, floating islands, ... 'n' stuff

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.