Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

Control Flow

2 (2.2%)

Arrays, Strings, Pointers, and References

8 (9%)

Functions

4 (4.5%)

Basic object-oriented programming

30 (33.7%)

A bit more advanced OOP (Composition, Operator overloading, Inheritance, Virtual Functions)

18 (20.2%)

Templates

8 (9%)

Other (Explain)

4 (4.5%)

Working with files?  (Streams)

15 (16.9%)

Total Members Voted: 89

[Blank Expression]

A potentially useful resource for non/new-coders who want to learn programming: http://learnpythonthehardway.org
Obviously this will teach you python but apparently it's a good grounding in how people learn to program, I've not read it but enough people I know have recommended it that I thought I'd pass on the link.

It is completely and utterly fantastic. Zed Shaw is one of my favorite people in the world and this book is absolutely awesome.

[Araph]

Thanks for all the advice and corrections! This thread is helping tons.

A potentially useful resource for non/new-coders who want to learn programming: http://learnpythonthehardway.org
Obviously this will teach you python but apparently it's a good grounding in how people learn to program, I've not read it but enough people I know have recommended it that I thought I'd pass on the link.

Thanks for the link; I know a bit about programming, only I know about Basic. Big difference between that and C++, though.

[TolyK]

There can't be "no good reason" if so many people do it. Your inability to give a balanced or nuanced answer makes your point unbelievable. Thank you for your time, your arguments are noted, but please don't bother.

To anyone else: Problem is, I'm writing something that should work both on linux and windows, and I'm too lazy to make my own makefiles or type in console compile commands. Code::Blocks handles all that perfectly, and I get to install and choose different compilers and linkers with the flick of a switch. Does Eclipse have that same functionality, and if so, where? Or is there another IDE that I actually should be using?

I use Code::Blocks and Visual C++ Express, they're both fine. I have an autoversioning thing in C::B.

...

how do you set up debugging and watches in Code::Blocks though? It's not working for me.

...

To beginners: I suggest Visual Basic (which has lots of documentation from Microsoft and is actually very intuitive) to start out, then your language of choice. VB is also a RAD (rapid development) programming language.

[Derekristow]

I started work on a clone of Outpost (http://www.outpostuniverse.net/outpost1.php), and it's going pretty well so far.

Spoiler (click to show/hide)

I've only got the drawing bit working so far though.  Next up is mouse collision, which is going to be absolutely horrifying.  Then I'll have to do something about the menu windows, still not entirely sure how to work that.  All of my forward though went in to how the buildings would update and communicate, so I've still got a lot to do.

I'm not going to mention this at the OPU forums. They've had a lot of failed projects, and if I end up abandoning this for some reason I don't want to add another to the pile.

[forsaken1111]

So I've run into a logic problem with a side project I'm working on and I'm not sure how to return an optimal or near-optimal solution so I wonder if anyone here might have a lead for us.

The project is an application to return a list of connections between locations based on the difference in value of trade goods at those locations. Connections each take up a 'slot' in the locations they connect, and each location has a variable number of slots.

For example:

City 1 has $80 wheat, $30 apples, $50 wood. 4 slots.
City 2 has $20 wheat, $35 apples, $80 wood. 2 slots.
City 3 has $30 wheat, $50 apples, $55 wood. 2 slots.

Simple example, but this should return something like:

Code: [Select]

City 1 <-> City 2 | Wheat [60]
City 1 <-> City 2 | Apples [5]
City 1 <-> City 2 | Wood [30]
City 1 <-> City 3 | Wheat [50]
City 1 <-> City 3 | Apples [20]
City 1 <-> City 3 | Wood [5]
City 2 <-> City 3 | Wheat [10]
City 2 <-> City 3 | Apples [15]
City 2 <-> City 3 | Wood [25]

SORT

City 1 <-> City 2 | Wheat [60]
City 1 <-> City 3 | Wheat [50]
City 1 <-> City 2 | Wood [30]
City 2 <-> City 3 | Wood [25]
City 1 <-> City 3 | Apples [20]
City 2 <-> City 3 | Apples [15]
City 2 <-> City 3 | Wheat [10]
City 1 <-> City 2 | Apples [5]
City 1 <-> City 3 | Wood [5]

ASSIGN

City 1 Slot 1 | City 1 <- City 2 | Wheat [60]
City 1 Slot 2 | City 1 <- City 3 | Wheat [50]
City 1 Slot 3 | City 1 -> City 2 | Wood [30]
City 1 Slot 4 | City 1 -> City 3 | Apples [20]
City 2 Slot 1 | City 1 -> City 2 | Wheat [60]
City 2 Slot 2 | City 1 <- City 2 | Wood [30]
City 3 Slot 1 | City 1 -> City 3 | Wheat [50]
City 3 Slot 2 | City 1 <- City 3 | Apples [20]

PRINT

City 1 wood -> City 2 [$30]
City 1 apples -> City 3 [$20]
City 2 wheat -> City 1 [$60]
City 3 wheat -> City 1 [$50]



We can get a good approximation of optimal by simply sorting all possible connections by relative value and then assigning connections from the top down. The problem we're running into is how to make it recognize when several 'less valuable' would be more optimal overall than one of greater value.

For example, say you have three cities and these cities each have Wheat and Wood for trade.

City 1 has $80 wheat and $20 wood. 1 slot.
City 2 has $30 wheat and $20 wood. 2 slot.
City 3 has $20 wheat and $60 wood. 1 slots.

Using the 'top down' method where you assign the most valuable trades first, the algorithm would assign City 3 to trade wheat to City 1, because the value of the city 3 to city 1 trade would be the highest.

City 3 wheat -> City 1 [$60]

But this leaves City 2 doing nothing, and the two trades the algorithm passed up would have been much more valuable total than the one it took.

City 2 wheat -> City 1 [$50]
City 2 wood -> City 3 [$40]

I know we won't get an optimal highest-value connection map without a lot more CPU cost attached, but is there any good way we can approach a semi-optimal solution without brute-forcing it?

If it matters, this is being written in Ruby but that's irrelevant really as it's a logic problem more than anything and I'm not sure how to approach it. Anyway, hopefully I explained that well enough. If anyone has any ideas how to refine this let me know.

[Nadaka]

forsaken1111: I am several hours late for bed, so I cant go very deep. but that looks like a relatively simple problem in numeric linear algebra and can I believe it can be solved with relatively simple matrix transformations.

[forsaken1111]

forsaken1111: I am several hours late for bed, so I cant go very deep. but that looks like a relatively simple problem in numeric linear algebra and can I believe it can be solved with relatively simple matrix transformations.

Well excellent, if that is true. The live data this is going to be run on includes 29 locations and 18 trade goods at each location, with each location having varying numbers of slots available, so if you have a relatively simple way to solve for the highest overall value I would love to see it.

[Siquo]

I'm not going to mention this at the OPU forums. They've had a lot of failed projects, and if I end up abandoning this for some reason I don't want to add another to the pile.

Not to put any pressure on you, but that Looks Awesome!

Forsaken, you could try Prolog, if you're into learning new languages, or find some kind of "pathfinding" algorithm so you can quickly and roughly determine whether a certain permutation is not going to be of any use? (I love your avatar btw, it makes me giggle).

Ninja'd by Nadaka: it's simple to calculate, but NP. When the number of cities or connections goes up, the calculation time goes up very fast. I think forsaken is trying to do it quickly and roughly in order to avoid waiting for days for the answer.

Ninja'd again:
29 locations, say 4 slots each, is 116 connections, that can connect in 18 different ways (we're counting doubles as well, this is rough), gives 7,0691+10^6026 permutations, minus a few doubles. Nice
Of course that's worst case scenario. Half of those 2000 connections is unprofitable, so you'd... no wait, you'd think they should be discarded, but it's possible that a permutation with an unprofitable connection is actually making more profit than one with just profitable connections.
... Nope, I can't think of anything beyond what you already thought of: just take the top profitable of those 2000 connections and start building your permutation from there. Perhaps you could build a few permutations from there and pick the best one?

[Shades]

but it's possible that a permutation with an unprofitable connection is actually making more profit than one with just profitable connections.

Actually it's not, but you'd have to include the possibility of just not having a connection from a city slot.

Sounds to me like generating a connection map and using one of the full tree parsing formulas would be a good bet. They do scale at O(n^2) though the larger your network the increasingly slower it'll be. Still with only 29 cities it shouldn't be noticeable.

A cheap, but non-optimal, solution would be to do your currently system but starting once with each city and see which gives you the best. There are situations where the best total doesn't contain any of the best routes but they shouldn't be a majority.

It looks like it should be a simple set operation but I don't see what it is off the top of my head.

[Siquo]

29 cities isn't the problem, it's the 18 different connections. I assumed all slots needed to be filled for a permutation, so you can "unslot" the non-profitable connections later, for the sake of calculating a total number of calculations. Or I'm just way off, it's been a while since I did this stuff

[Virex]

I started work on a clone of Outpost (http://www.outpostuniverse.net/outpost1.php), and it's going pretty well so far.

Spoiler (click to show/hide)

I've only got the drawing bit working so far though.  Next up is mouse collision, which is going to be absolutely horrifying.  Then I'll have to do something about the menu windows, still not entirely sure how to work that.  All of my forward though went in to how the buildings would update and communicate, so I've still got a lot to do.

I'm not going to mention this at the OPU forums. They've had a lot of failed projects, and if I end up abandoning this for some reason I don't want to add another to the pile.

Mouse collision can actually be quite easy, depending on the amount of support your library is giving. In the case of a 3D game you can draw a ray from the camera through the front of the camera's frustum (a truncated pyramid that determines what should and should not be drawn) till the back of it. Then you can do a ray intersection check to find the object the player is clicking on. (both ray drawing and intersection checking tends to be available in most engines.
That is of course, assuming you're doing 3D. If it's 2D you need size bounds for your object so that you can just plug in the x and y coordinates of the mouse and get the object the mouse is hovering over.

[GlyphGryph]

Actually, Forsaken forgot one component of this problem, when he described it to me.

Each city can make a connection on a good multiple times (even to the same city), each city should only have at most 3 connections for any particular good in it (to any other city). Maybe it doesn't make it much more complex, but something to keep in mind.

[forsaken1111]

Actually, Forsaken forgot one component of this problem, when he described it to me.

Each city can make a connection on a good multiple times (even to the same city), each city should only have at most 3 connections for any particular good in it (to any other city). Maybe it doesn't make it much more complex, but something to keep in mind.

Indeed, I forgot about that. Each location can export or import a good multiple times, and the algorithm needs to be able to limit the total trades of a specific good to an arbitrary number as well.

I think forsaken is trying to do it quickly and roughly in order to avoid waiting for days for the answer.

That's it exactly. I know full well that I won't generate an optimal connection map without a super computer and a brute-force method but I'm looking for some logic that will create a 'good enough' solution which is slightly more accurate than the top down model if such a thing exists. Simply slotting the most profitable connections will generally create a -good- model so if that's all we can do, we'll work with that.

[Lord Dullard]

A potentially useful resource for non/new-coders who want to learn programming: http://learnpythonthehardway.org
Obviously this will teach you python but apparently it's a good grounding in how people learn to program, I've not read it but enough people I know have recommended it that I thought I'd pass on the link.

It is completely and utterly fantastic. Zed Shaw is one of my favorite people in the world and this book is absolutely awesome.

I'll give this a look later. Thus far my method for learning any new coding language has been 'blunder around until I've got some semblance of a working knowledge of how to use it'. Probably not the most efficient modus operandi.

There are a number of new languages I'd really like to learn. I have very little experience with any sort of net-based coding and in this day and age learning to implement communication and connectivity into programs I write is something I'm sure I'll want to be able to do.

[Shades]

I have very little experience with any sort of net-based coding

You want to look at 0MQ, this is actually true for anyone interested in multi-threaded programming too.