tile based map walking problem

I made a little DOS engine once that was able to have different hights and such...it used a simple "3D" mesh to draw the ground (not real 3D as there was no Z axis...just X and Y)...basicly the map contained a "texture" pointer, a byte for "effects" (walk/no-walk, and others) and for bytes indicateing "Y-offset" of each corner (there were "wall" textures too...but that may be more confuseing right now).

the characters X and Y position only represented the "flat" world...basicly I would use the X and Y to find out which tile the character was standing on...look it up in the map...then figure out the point within the tile the character was standing on then interpolate what the "Y-offset" should be basied on the tile Y-offsets....

then I ran a "screen collision detection" routine to figure if the sprite was onscreen (checked with X and y + offset, seeing if the sprite graphic was within the screen area)...this is a over simplification, but hope fully you get the idea....this generated a list of onscreen sprites...I then sorted this list basied on thier Y location (without the offset)

Then to draw the screen...I would draw one row of tiles (actually drew them as polygons...instead of drawing them as regular tiles I would pass the rendorer the screen cords (if they were flat tiles...but I would add the Y-Offset to the Y value)...once a row across was drawn...I would then draw the sprites on the list with a Y value that was less then the last row of tiles (but draw them with the Y-offset)....then once I found a sprite with a greater Y value (meening it''s on another row of tiles) I would set the list pointer to it and delete all the previous tiles from the list. draw the next row, and any sprites on it...repeat until done.

It worked pretty good...but was slow (mostly due to the Pentium 60 I wrote it on, and the fact that I never tried to optimize it...especialy sense it had to redraw the entire screen, "tiles" and all, every frame)