I''m working on a project for my Computer Graphics class this semester. I''m making a game that uses a Wolf3D style raycast engine. Instead of creating a level editor I''ve decided to create the levels as bitmaps (drawn in the paint program of my choice), and then write a program that scans the bitmaps and coverts the lines and curves in the bitmap into line segments that will represent the walls in the game. The trouble is my search for such an algorithm on Google has come up dry. I have some ideas, but I am also a firm believer in not reinventing the wheel, at least not without seeing what''s already been done first. Has anyone done this or something like it before, or do you know of any resources I could refer to, or do you just have a good idea. I''ve already got the code to crawl along the walls pixel-by-pixel in the bitmap. Just to make sure I''ve satisfied the "homework post" requirements: I''m going to, and want to do the entire project myself; I''m just stuck on an approach to take in a single portion of the project. I''m not even looking for code, just an algorithm.

Thanks. Sometimes the hardest part of searching for information is knowing the terms!

By the way I''ve come up with an algo that works nicely (I thought of it just after I posted, of course...). If anyone''s interested, here goes:

Walk recursively through adjacent pixels. Anchor a point at your starting point (call it StartVertex), and then for each new pixel traverse the line from StarVertex to CurrentVertex and see how many of the desired pixels you hit. If the number of misses exceeds a tolerance setting, back up a pixel, anchor the StartVertex there, and create a line from the old StartVertex to the new StartVertex. There are a few more details to take care of but this is the general idea, and it does work (I coded it this morning). Thanks for the help, the project''s moving along nicely.

Okay, I guess I fibbed a little. What I meant was that I will be raycasting and that I won''t be drawing the tops of walls (and all walls are uniform height). However I do (or did) intend to allow walls at arbitrary angles to each other, meaning curved walls are definitely an option. I realize this is not simple, but even if I don''t do this as my project, I do want to do it for fun. As for the complexity of the image converter, so far it hasn''t been bad at all. I''ve already got it 80% complete (in 3 or 4 days). The image files are bitmaps with walls drawn in a paint program as lines, circles, boxes and other such line-defined curves. All walls are a single pixel thick, so a line in the bitmap of a single pixel thickness is detected as a wall. There is a reserved color that is off limits for walls (it''s white right now <255,255,255>); any other color can be a wall, and the colors can be associated with textures and other properties. But like I said, the image detection/conversion has actually been pretty much a piece of cake, although getting it completely perfect is not. The reason I don''t want to build my own editor is that the features I would want in the editor are the same features found in any popular paint program. Since this software already exists, why build my own? The conversion program is not nearly as complicated as designing my own paint program featured editor.

Of course if I just used squares for the walls this wouldn''t be an issue... oh well, I guess I''m just a glutten for punishment!

Thanks. No I probably won''t be distributing the engine (I doubt it will turn out that good, and besides it''s going to be several steps behind the tech. curve now...), but it should be fun. I read LaMothe''s Tricks of the Game Programming Gurus among others and I''ve always wanted to make a ray-traced 3D game, so I figure this is as good a time as any, even if the technology is a bit dated.