Print

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

[Mikademus]

Ambitious and interesting! I'm looking forward to the tests, but I would like to read the code before commenting on the results, off course.

[Veroule]

Ambitious is definitely the operative word here.  I am still mucking around with the data structures and the memory management portions of this.  I think I have all the data structures sorted out into the happy medium between memory and speed.  The management routines I am writing are a little bit greedy, but they are designed around trying provide a more threading friendly environment.  Maybe by the end of the week I will have reached initial testing of a basic A* implementation.

After that things should fall into place rather quickly for testing all the possible variations I have considered.  My notes for implementing them are pretty clear.

Once everything checks out for being able to path correctly then I will move to devloping the 2 phase pathing.  At that point I will probably need some help from the DF utility community to produce a method for grabbing real DF maps into my test app.  Having those kind of real test maps will be very important for the finished product.

Overall I expect it to be about a month before I can supply an app that tests all the variations and reports interesting time information.  I would probably not include the source code at that point, as I would consider it still under devlopment.  The app would have to be capable of loading, saving, and randomly generating mazes in order for a test release.

[numerobis]

I just whipped up a pokey little framework for testing searches.  Nothing fancy at all.  The idea is that fundamentally what probably dominates the runtime is how many grid cells you read, so all I support is reporting how many grid cells you read.  I have a super-simple file format -- just a text file with '#' for walls and '.' for navigable areas.  I don't require stairs to go up, and I allow going diagonally in any direction.  If you care, feel free to fix the code:

Download.

Type 'make' and it should build you a program imaginatively called 'main'.

Run ./main test-input and it will report how many grid cells were read during 500 runs, each run consisting of a random source and a random destination.  Note that my pathetic little version of A* is molasses-slow (and probably buggy).  It's meant to show how to get statistics, not really meant to show how to write the awesomest A* in existence.

Ideally there'd be a more realistic benchmark: we aren't actually seeing random location -> random location pathfinding in DF.  But I only wanted to spend at most 2 hours on this project.

The main thing missing from this is a verifier: making sure that the path you find actually gets to the destination.

[Veroule]

Sorry, but no real news to post.  Just to give everyone an update, I got bogged down in the memory management parts of this.  My requirements for effficiency pay attention to both how memory is used and how often data has to be replicated.  My work and some other projects also demanded significantly more attention than anticipated last week.

Numerobis, your code does preform its function as an A* example.  It is still OOP spaghetti.  OOP earned a bad reputation with some elder programmers because it wasn't done right.  The particular pieces you use and the way in which you use them exhibits most of what is wrong with OOP.  OOP by definition doesn't know anything about what/how a higher level object needs or will do.  Often lower level objects aren't properly designed to be overidden with specific code and instead are coded around.  You don't even code around the weaknesses in the onject you are using to try to make a better object.

I am sure it will bug some people, but I am coding this in flat C.  It will be full of pointer math, but I make it so verbose that it is impossible for a compiler to mess it up. Before I am happy with it, I will have reviewed all the assembly produced and done as many adjustments as I can to the C sources.  It is my intention to actually go so far as putting in compiler defines to handle me specifically retuning the final assembly code.  That assembly code would be available as a replacement when both compiler and machince settings matched my tuning.

Anyhow, long ways to go before I am happy with anything to release.

[Mikademus]

I am sure it will bug some people, but I am coding this in flat C. 

Code it in Intercal or Brainfuck for all that it matters. The only important thing is that if you arrive at something you document the concepts fully and intelligibly, so everyone can implement it in their language of choice.

That said, you're probably giving yourself unnecessary headaches when you could have gone Python, Ruby, SML, or OOP C++/Java...

[H]

It doesn't bug me that you are programming in C, it bugs me that you are worrying about the wrong sort of optimizations.  DF is slow because of its choice of algorithms is sub-optimal, not because its assembly code hasn't been fine tuned.  Worrying about such issues is literally the last thing you should do.  For example, I was once wrestling with a speed issue around a hash table; when the table got too big the program was unacceptably slow.  Back then my first instinct was to start fine tuning things in the same way you are.  That helped, but not enough.  And, after several long nights, I realized that the hash function was bad.  Once the hash function was improved speed became acceptable.  Indeed the original version could have been made fast enough simply by changing the hash function.  The moral here is to always try to find the greatest speed improvements with the least work, and that's almost always going to have to do with the computational complexity of the algorithm.  Another moral is to always program a version in a high level language like Java or Python where you are forced to make improvements at the level of computational complexity and then move to a lower level language, to avoid the wrong sorts of temptations.

[Antsan]

I guess, necroing this thread just out of pure interest isn't the best behaviour, but I don't lnow how else to get, what I want.
So: Any results or improvements? Benchmarks for different algorithms? Algorithms?