kalimdor_wilson ([info]kalimdor_wilson) wrote,
@ 2006-03-04 19:54:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Dammit, I used to be good at this...
So here I sit, working on my generalized version of the pathfinding code. The original that I blogged about was both inefficient, leaked memory, and only worked for the very simple map I had created.

I want a pathing program that is flexable enough to work with whatever I throw at it. And I want it to be very portable and usable for almost any environment, so I'm coding it in straight C.

A flexible pathfinder. Working with unknown map types. Using lists or trees that also have to deal with any kind of data.

In C.

If any Real Programmers are reading this, they're probably yelling at the screen, "You fool! Your dealing with objects! That code should be object-oriented. Save yourself the pain and use a better language! Fool! Amature! Naive amature!"

Well... what are my alternatives? C++?

C++ and I go waaay back. When I first met C++ I thought it was the greatest, bestest programming language ever! All the familarity of C with all the coolness of object-oriented programming! My first C++ programs showed me a brand new world, and I was smitten. As my programs got more complicated, I started having troubles. "No problem!", I thought. As I learn more of the language, this too shall pass.

I even got into an argument with my Computer Science professor (CS 101) about it. He hated C++. Thought it was an abomination. I thought he was just from an earlier generation of computer scientists that just couldn't see this Wonderful New World that had overtaken their stodgy, ancient ideas.

(Any Real Programmers reading this are probably laughing their asses off at my expense. And they have every right to.)

It wasn't until I worked for Real Networks that the curtains of infatuation were ripped down and I got my first view of The Truth About C++. Real had this tendancy to hire brilliant programmers. I felt like a fraud just walking among them. For the first time in my life I met coders that I would assign the title "Master". They were that good.

Then I was thrown into the abyss of the RealPlayer source code.

See, here's the thing... pure object-oriented programming in C++ is insane. When you throw away the last threads of pure C and work with a fully object-oriented programming model in C++... well, it's difficult to describe to someone who's never used C++ this way. Most C++ coders who still like the language mainly write C code with a few useful snippets of C++ thrown in. They don't know, as I know now, the madness that lies down that path.

At Real, I would work on the source code, putting in my assigned tasks and thinking, "This codebase is madness! MADNESS!! There has to be a better way to implement this particular thing I'm looking at!"

Then I would go home and try to work out a better model.

What I would wind up with would be almost exactly like what they had already written, but more clunky and less flexable. That "insane" code I had seen that day at work was actually the best possible solution. It was written by Masters, after all. I was not better than them because they were "brilliant", whereas I am merely "smart".

This, my friends, is when The Truth About C++ began to reveal itself to me. I was enlightened.

Crap. So C++ is out. What else could I use? Objective-C? It's the native language of the Macintosh now, but you don't see it on many other platforms. My code would be far less portable and tied to this one system. I also don't know how much overhead it would add to the pathfinding code, especially since I'm very new to Objective-C and don't really know how to wield it correctly.

C#? Started out as a Windows-only thing but it's been implemented for Unix (and thus all newer Macs that run OS X). But I've used C# in my last programming job and there are things about it that bug me.

I don't know Lisp or Smalltalk, and I don't know if those languages are fast enough for the uses I'm going to be putting my pathfinding code to. Nor do I know if they're even well-suited for the task.

So C it is.

This, of course, brings along its own problems. What part of the program owns what memory? What if two or more parts of the program use it? Which part is responsible for finally freeing the memory when it's no longer needed? If I'm dealing with data of an unknown type, how do I work with it?

My first stab at this project had me writing what basically amounted to an object-oriented framework for C, only without type-checking and adding data and code overhead (therefore being both slower and using more memory). I might as well use C++ if I'm going to go down that path. And I am not going down that path. Never again will I go down that path.

Ironically enough, this is forcing me to become a Real Programmer. At least for the C programming language. It's been so long since I did any actual programming that I can feel my brain stretching. I have to take breaks because my brain gets tired. And I can feel myself getting better at this. Piece by piece. Bit by bit (punny!).

So it's cool. My stint as a professional programmer both burned me out on programming and also totally destroyed my ability to write good software. True programming is an art form. In the "real world" you just have to get the code out the door under deadline, no matter how sloppy or ugly it is, and just hope that the client never uses it under conditions where any hidden bugs will make it explode and dump core / segfault / general-protection-fault / halt-and-catch-fire.

But now it's just me and the machine. No deadlines. I can take the time to try to craft the code, instead of just slapping down something that works under simplified test cases. It's fun again!

My code is still... I would consider it functional and sort of elegant, but still merely "okay". I still have a long ways to go in regaining my former skills (and hopefully surpassing them), but for the first time in years, I'm looking forward to it.



(Post a new comment)


[info]agentcooper
2006-03-05 03:36 am UTC (link)
Well, having not yet downloaded and perused your code, I don't have much to offer. However, it seems you should be able to do everything you want in C. It needn't take more time or space.

"What part of the program owns what memory? What if two or more parts of the program use it? Which part is responsible for finally freeing the memory when it's no longer needed?"

You don't need objects to fix this; operating systems are full of design patterns, but implemented in C. Think "resource manager" and "handles." Have factories that load/destroy units of data and pass out handles to them.

Which leads into the next question:

"If I'm dealing with data of an unknown type, how do I work with it?"

You want to code to one common interface, and then reimplement that interface for each type of data. Think "iterator" or "facade" design patterns. Or device drivers. You can use arrays of function pointers, initialized according to the type of data. pGetNeighbor(handle, direction); (which really is the same as node.GetNeighbor(direction)).

Anyway, keep at it. It looks like a fun project. I should build and run your code this weekend. This article on A* looked very promising; have you read it?

(Reply to this) (Thread)


[info]kalimdor_wilson
2006-03-05 04:08 am UTC (link)
Think "resource manager" and "handles." Have factories that load/destroy units of data and pass out handles to them.

That was part of my second stab at it. The problem is that, due to the size of map I hope to eventually use, I'd wind up using up to 24 megabytes more memory per pathfinding character.

So if I only have 10 NPCs on my map and they all are engaged in medium-to-worst-case searches... that's a potential of 240MB of extra memory that would be used. I want to keep things lean because I need them to scale. Really, truely scale.

Function pointers, on the other hand, make my inner geek jump around with glee. I've never used them in a serious manner before, but now they're a core part of the toolset I'm building.

They're also how I've opted to deal with the different data types. My new pathfinding code should be able to handle whatever kind of map you desire, from simple grid-based maps to node graphs.

The real trick is finding just the right balance between flexability and simplicity.

Think "interfaces" but a little more primative.


"I should build and run your code this weekend."

Keep in mind that that's the proof-of-concept version I wrote. I don't have any of the new code posted yet, but I will when it works. It'll take a little while because my a-star implementation lets the user decide on if the opened and closed lists will be lists or ordered tress (more memory usage, but should speed it up quite a bit).

You'll also need SDL, but it's stupidly easy to install on Mac OS X now. Hooray!

"This article on A* looked very promising; have you read it?"

Hadn't seen that before. It communicates the idea better than the book that I have, too!

I'm just happy that I was able to both comprehend it and implement it successfully on my second try (which is the source that's currently available).

Someday I'll be a good programmer again!

(Reply to this) (Parent)


[info]kalimdor_wilson
2006-03-05 04:18 am UTC (link)
Oh man... the book I have has the A* alogrithm searching for adjacent nodes on both the opened and closed lists, but it's only necessary to search the opened list!!

ARGH!

*smacks brain around*

And it's so obvious, too!

(Reply to this) (Parent)(Thread)


[info]agentcooper
2006-03-05 04:45 am UTC (link)
:-D

Glad I could help.

(Reply to this) (Parent)


[info]aerolyn1
2006-03-05 04:44 am UTC (link)
LOL - Wow Brad. A real post. Like, with words and shit. Neet! Remember the Tron game you tought me C++ on? That was fun... although I'd have never admitted it back then.....

(Reply to this) (Thread)


[info]kalimdor_wilson
2006-03-05 05:00 am UTC (link)
"Wow Brad. A real post. Like, with words and shit."

Yeah! Innit neat?

I used to do more "real blog posts" in the past, before I got my camera and turned it turned into a photoblog / political-rant-space.

Here's to more future "real blog"s!

*clinks glass*

(Reply to this) (Parent)(Thread)


[info]agentcooper
2006-03-05 08:13 am UTC (link)
Uh. I, for one, far prefer your photographic uniqueness to rants about software. :-)

(Reply to this) (Parent)(Thread)


[info]kalimdor_wilson
2006-03-05 04:51 pm UTC (link)
Maybe I should do photographic rants about software politicians...

(Reply to this) (Parent)


Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…