06 Sep, 2011, Rarva.Riendf wrote in the 41st comment:
Votes: 0
Runter said:
I think like 16 megs is about what mp3 players have. ;)

https://vpscheap.info/compare-vps.html

That's 10 gigs hard drive, 200G bandwidth, 128M ram, free backups, managed hardware for $1.50 per month or $15 dollars a year. I don't really understand running any software on something so archaic these days. Just skip a coffee and pay for a good server. :p

Heh on the other hand it forces you to actually check your code efficiency and makes you think of freeing memory :) (and I totally agree on the recursion thing, I found a lot of those in the code I have, and even some bubble sort code instead of using qsort)

I have a heavily multithreaded code to optimize char eq that I optimized quite a lot because I am limited in power. (my best comp is a quad core 8200 with 4 gig of ram)
I started with this code with a pentium 3ghz and 2gig ram :) The limitation actually helped me a lot as since I was hitting the ceiling fast I had to actually think about it instead of just relying on pure power.
06 Sep, 2011, David Haley wrote in the 42nd comment:
Votes: 0
Runter said:
It shouldn't be surprising that people in C would rather use recursion, for example, to solve certain problems better done by iteration because it's so onerous to just implement and test a list or map structure in C.

Well, for the sake of the argument, I'm not sure I agree with this. For recursive problems that involve tracking state – especially a search algorithm that needs to know where it's been – you have to maintain these maps/lists/queues anyhow.

And also, I think a case can be made fairly easily that you could move to C++ and sacrifice little speed and gain a great deal in terms of container structures.

Runter said:
And I stand by my statement that it's easier to implement the correct algorithm in a higher level language, and therefore, it'll be implemented more often more correctly in a high level language.

Yes, agreed. I would add however that people working in a high-level language are also more likely to introduce sometimes glaring inefficiency if they're not aware of the actual implementation of a data structure. That said, for the most part, data structures are implemented intelligently for their common use cases. But for instance, if you use a straight array to manage your queue, you're likely to hurt yourself; the array makes it easy to pop off the first element semantically, but that will cost you dearly in efficiency.
06 Sep, 2011, Runter wrote in the 43rd comment:
Votes: 0
Well, for a search algorithm it doesn't have to use a map/list/queue. It can just mark the node as it visits them to prevent covering old ground. This shouldn't be anyones preference, but it's probably easier than managing a list in C, and a good example of what I'm talking about.

Quote
And also, I think a case can be made fairly easily that you could move to C++ and sacrifice little speed and gain a great deal in terms of container structures.


Isn't this exactly what I'm talking about? Moving to a higher level language to lose a little and gain a great deal? Obviously, we're going to disagree with what a little and a great deal is here, but it's not uncommon for people to believe that C++ is sacrificing too much and gaining too little. So I'm not at all convinced that something higher level is too extreme, either. Especially as hardware gets better and better.
06 Sep, 2011, David Haley wrote in the 44th comment:
Votes: 0
Quote
it's not uncommon for people to believe that C++ is sacrificing too much and gaining too little.

Yes, well, moving from C to C++ isn't quite the same as moving from C to Lua/Python/Ruby/etc…
06 Sep, 2011, Silenus wrote in the 45th comment:
Votes: 0
David Haley said:
Silenus said:
This link of yours seems to point to a Datalog with negation thing i.e. Prolog without terms but with negative clauses.

There are free terms.

Silenus said:
I am not sure which project you are referring to in this case but I did not read this particularly carefully- seems like some game playing competition of sorts.


So this variant of datalog includes term trees? This would seem to be a bit of a misnomer then. So A* uses scoring as opposed to distance functions? i.e. no triangle inequalities (since this would make it a metric I suppose).
06 Sep, 2011, David Haley wrote in the 46th comment:
Votes: 0
Quote
So A* uses scoring as opposed to distance functions? i.e. no triangle inequalities (since this would make it a metric I suppose).

I don't understand what you're asking.

A* uses a heuristic to judge how likely a state is to be near the goal state in the search space. In some search spaces, "nearness" is literally a geometric distance metric. In other search spaces, "nearness" might be how many boolean satisfaction flags are on, and "distance" would be defined as the number that are off.

A* is guaranteed to return the optimal solution under some conditions, for example, if the heuristic has no triangle inequalities. But those are not necessarily geometric distance.

You can use the terms "score" and "distance" interchangeably as long as you are not understanding geometric distance.
06 Sep, 2011, Silenus wrote in the 47th comment:
Votes: 0
I was just wondering if there was a "metric" requirement for A*. I think metrics generalize the notion of distance(I think geometric is probably wrong- topological is more accurate). I think I saw this in some ugrad analysis text running around bookstores in Hong Kong (I think the popular one by Rudin).

Most versions use the Euclidean distance or maybe Manhatten(for A*). Are fib heaps still the preferred queue type?

Runter- yes getting algorithms right in a low level language like C can be challenging (I think for the more complicated ones you could toss it to a pretty seasoned C programmer and they might not be able to have it bug free and efficient on the first try). Programming like this has it's place though but for the majority of application oriented tasks I suspect something like Ruby/Lua/Python has a lot of advantages. Lower line counts runtime checking = a much more friendly environment and few "catastrophic" errors. But as David indicated- getting it exactly right often requires low level skills and understanding of issues like caches and machine level stuff (a lot of which is not documented unfortunately).
06 Sep, 2011, David Haley wrote in the 48th comment:
Votes: 0
Quote
Most versions use the Euclidean distance or maybe Manhatten(for A*).

This is only because it is simplest to demonstrate the algorithm with visualizable search spaces, e.g. with robots navigating some physical space.
06 Sep, 2011, Silenus wrote in the 49th comment:
Votes: 0
Thanks David. I will look it up when I am no longer touring around.
06 Sep, 2011, Runter wrote in the 50th comment:
Votes: 0
Quote
getting it exactly right often requires low level skills and understanding of issues like caches and machine level stuff (a lot of which is not documented unfortunately).


Lol? I know you probably believe that and I don't mean to be rude, but-

Does driving a race car mean you have to know how to engineer the alternation system to get every drop of energy out of the battery at top efficiency? I think we know the answer to this. Even C isn't the lowest common denominator, and our disagreement is really a question of the appropriateness of something higher level than C for most software.

Getting it exactly right is different from fine tuning. Getting it exactly right requires skills that don't really involve understanding caches or machine code for most (even complex) algorithms. The question of whether or not something runs better when you write it in assembly or C is separate from that of "can I write this in C without knowing assembly?" ; "Can I implement this pattern?"

The classic CS patterns are most often (and most easily) correctly implemented in higher level languages. Just look at example pages where people use a high level language to demo how to correctly implement it. It's just easier. Writing in C is a pain, and as such, it has people consider "Do I really need this algorithm in the first place?" That's a dangerous sentiment to have, but it's also a necessary one when you have a deadline tomorrow and you've weighing writing the most correct code vs what works.

That's the realistic world we live in. Once upon a time C was considered a high level language. If hardware resources were infinite nobody would write in C and this debate would be silly. I'm asserting that we're nearer to that point than you may think. I think for most software you have such an abundant amount of resources that it makes little difference. If the only thing we cared about was making the machine work better, we'd spend our lifes carefully writing machine code. But that's patently absurd, and I think using C for stuff other than drivers & extensions & extremely sensitive programs these days is also patently absurd.
06 Sep, 2011, Silenus wrote in the 51st comment:
Votes: 0
Runter I believe I already said that so I am not sure why you are upset in this case.
07 Sep, 2011, Runter wrote in the 52nd comment:
Votes: 0
Silenus said:
Runter I believe I already said that so I am not sure why you are upset in this case.


I'm not upset. I just disagree.
07 Sep, 2011, Silenus wrote in the 53rd comment:
Votes: 0
What do you disagree with? I thought more or less we are/were making the same point.
07 Sep, 2011, Tyche wrote in the 54th comment:
Votes: 0
Rarva.Riendf said:
The bottleneck I was suffering was outside of the method, because to calculate the path it would use an easy recursion method. I missed those 3 or 4 lines, so I thought that the lag was coming from the method itself, as I was using it for the whole world instead of an area. And there was many comments hinting at it should be limited to areas because of the lag it could induce.


And that is I posed the question about whether anyone was reading the code.
Rarva.Riendf said:
Indeed, I identified the real culprit of the bottleneck: Instead of storing the path while it is calculated previous coders had the horrible idea to calculate path, move the first room in it, recalculate path from there, till it find the last room…hugh.

It was in fact your "horrible idea" of wrapping their code in a loop and using it to build a path.

Rarva.Riendf said:
…so I guess they just used it for themselves to build path between areas.

I don't believe that.
07 Sep, 2011, Rarva.Riendf wrote in the 55th comment:
Votes: 0
Quote
It was in fact your "horrible idea" of wrapping their code in a loop and using it to build a path.

Nope it was not, it already used this sytem in track, the only thing I added in the find_path was to only visit room the player had visited…
track "mob" map would give the path, using recursion, I was using this result first in a quick hack to test the possibility to give it to players (I would just create a mob xxx in the room , track xxx map to it and get the result) (and btw when I was a player I actually saw immortals doing just that…mload or tansfer a mob to track to them to build path we now have in helps)

But heh call me liar I do not care…
07 Sep, 2011, Tyche wrote in the 56th comment:
Votes: 0
Rarva.Riendf said:
Quote
It was in fact your "horrible idea" of wrapping their code in a loop and using it to build a path.

Nope it was not, it already used this sytem in track, the only thing I added in the find_path was to only visit room the player had visited…
track "mob" map would give the path, using recursion, I was using this result first in a quick hack to test the possibility to give it to players (I would just create a mob xxx in the room , track xxx map to it and get the result) (and btw when I was a player I actually saw immortals doing just that…mload or tansfer a mob to track to them to build path we now have in helps)

But heh call me liar I do not care…


Next time post the code YOU are running. Nobody here is psychic and should have to guess at how YOU fucked it up.
And by YOU, I mean collectively "YOU, the coders, your little brother, invisible friends and/or the imms on YOUR particular game"
as opposed to the code you linked to, that the rest of us are familiar with and may be running.
07 Sep, 2011, Rarva.Riendf wrote in the 57th comment:
Votes: 0
Quote
Next time post the code YOU are running. Nobody here is psychic and should have to guess at how YOU fucked it up.
And by YOU, I mean collectively "YOU, the coders, your little brother, invisible friends and/or the imms on YOUR particular game"
as opposed to the code you linked to, that the rest of us are familiar with and may be running.

Yeah would have been better, but the code was in progress did not compile at the time since I was working on it. (to be clear:the slow version was working, but I was in the process of changing it, would have had to extract the working branch..but the question was not why it was slow in the first place)
The algorithm was exactly the same, and the fact that people told me that indeed the problem was probably not there pushed me to look elsewhere.
And the discussion also gave answer for others problems that would probably not have been raised.

And btw:the method do calculate the full path, it just does not store it…
25 Jan, 2013, Rarva.Riendf wrote in the 58th comment:
Votes: 0
Archeology is fun. I decided yesterday to take a look back at track again, as I was cleaning and optimizing code here and there using sensible type instead of int everywhere.
I wanted to know how effective would be changing the door order in wich room are visited.
So I tried a simple thing: calculate the path with the 'fixed' order, then feeding it with the order from the path it just calculated, (if your path had a total of 5e 20s and 6w the order would be swe as an example)
There is one surprising case where I finally parsed a little more room (around 100 out of 15k) but some result where really impressive,
57% less room visited on 1036354 parsed to find all my initials paths. (from the main city to all other areas and reverse)
And take in account that I only change the door order once. I am now coding a way to change it every iteration, as optimal order in the middle of path is obviously not the same than at the beginning. (will code that soon, as I am curious about the possible gain (will time it as well, as the optimal door order calculation will add some loops.)

It was pretty obvious there would be a gain, surprising that one case could be a loss (even if slightly), but now I can put a figure on it.
25 Jan, 2013, quixadhal wrote in the 59th comment:
Votes: 0
I assume you're talking about the "estimate" to use for an A* type path algorithm?

It would indeed make sense to not only use the distance, but also the general direction, in that estimate. Since you don't know the path, but you might know the destination's coordinates, you can compare to your own and try exits in that general direction first. It may throw you in cases where there are large impassable mountain ranges to get around, but on average it'd probably be right ore often than not.
26 Jan, 2013, Rarva.Riendf wrote in the 60th comment:
Votes: 0
Yeah I will now generate a map to get the general direction so I get a better door order even when I dont have a pregenerated path.
40.0/61