/* $Id: map.hpp,v 1.74.4.1 2006/01/20 11:23:31 chfreund Exp $ */

/******************************************************************************/

#ifndef _MAP_HPP_
#define _MAP_HPP_

/******************************************************************************/

#include <SDL.h>

#include "global.hpp"
#include "string.hpp"
#include "serializable.hpp"
#include "serialize.hpp"
#include "mapmemory.hpp"
#include "flag.hpp"
#include "theme.hpp"
#include "graphics.hpp"

/******************************************************************************/

// forward declaration needed for method ServerMap::createFromTheme
class World;

//////////////////////////////////////////////////////////////////////
// Map contains the 'static' part of the battleground (e.g. a
// background, the foreground pixels, flags for each pixel etc)
//////////////////////////////////////////////////////////////////////

/******************************************************************************/

class Map {
	protected:
		//! sets entire flag field to zero
		void initializeFlags( void );
		//! m_sizeX is the width, m_sizeY the height of the map
		Uint32 m_sizeX, m_sizeY;
		//! A flag field e.g. for marking obstacles
		MapMemory<Flag> m_flags;
		
/******************************************************************************/

	public:
		Map( Uint32 sizeX, Uint32 sizeY )
			: m_sizeX( sizeX ), m_sizeY( sizeY ),
			  m_flags( sizeX, sizeY ) {
			initializeFlags();
		}
		
/******************************************************************************/

		Map( MapMemory<Flag>& flags )
			: m_sizeX( flags.getSizeX() ), m_sizeY( flags.getSizeY() ),
			  m_flags( flags ) {
		}
		
/******************************************************************************/

		virtual ~Map() { }
		
/******************************************************************************/

		// returns the width of the map
		Uint32 getSizeX() const {
			return m_sizeX;
		}
		
/******************************************************************************/

		// returns the height of the map
		Uint32 getSizeY() const {
			return m_sizeY;
		}
		
/******************************************************************************/

		// returns a pointer to the flag container
		MapMemory<Flag>* getFlags() {
			return &m_flags;
		}

/******************************************************************************/

		//! \name methods concerning map creation from a theme definition
		//@{
		//! creates a map from a theme
		void createFromTheme( Theme& theme, World& world );
		//! fills the map with random circles
		void fillWithRandomCircles();
		//! places the passed sprite as map stuff of passed material
		void placeMapStuffItem( const Sprite* const item,
		                        const Sprite* const flags,
		                        const Uint32 x, const Uint32 y,
		                        const int material,
		                        const bool smoothable = true );
		//! places the passed sprite as map stuff of passed material
		void placeMapStuffItem( const Sprite* const item,
		                        const Uint32 x, const Uint32 y,
		                        const int material,
		                        const bool smoothable = true ) {
			placeMapStuffItem( item, item, x, y, material, smoothable );
		}
		//@}

		void displayFlags();
		bool saveFlags( const char* comment );
		
		virtual void getColorAt( const Uint32 x, const Uint32 y,
		                         Uint8& red, Uint8& green, Uint8& blue ) = 0;
		virtual void setColorAt( const Uint32 x, const Uint32 y,
		                         const Uint8 r, const Uint8 g, const Uint8 b ) = 0;
		virtual void setColorAt( const Uint32 x, const Uint32 y, const Uint32 color ) = 0;
		
/******************************************************************************/

		void destroyEarthPixel( const Uint32 x, const Uint32 y, const Flag mask ) {
			Flag& flag = m_flags.getReferenceTo( x, y );
			
			if( (flag & Flags::OBSTACLE_EARTH) && ! (flag & mask) ) {
				LOG( 5 ) INFO( "Map::destroyEarthPixel: at (%i, %i)\n", x, y );
				flag = 0;
				setColorAt( x, y, 0, 0, 0 );
			}
		}
		
/******************************************************************************/

		void destroyEarthPixelClip( const Uint32 x, const Uint32 y, const Flag mask ) {
			if( x < m_sizeX && y < m_sizeY ) {
				destroyEarthPixel( x, y, mask );
			}
		}
		
		//! combines all flags in the specified rectangle with binary OR
		
		/*! Combines all map flags in a rectangular area with the binary
		 *  OR operator and returns this value. The rectange area is
		 *  specified by passing its uper left corner (x1,y1) and its
		 *  bottom right corner (x2,y2). This means that the rectangle
		 *  includes the points (x1,y1) and (x2,y2).
		 */
		Flag getOrCombinedFlagsInRect( Sint32 x1, Sint32 y1,
		                               Sint32 x2, Sint32 y2 ) {
			if(   x1 < 0               )  x1 = 0;
			if(   y1 < 0               )  y1 = 0;
			if( ++x2 > (Sint32)m_sizeX )  x2 = (Sint32)m_sizeX;
			if( ++y2 > (Sint32)m_sizeY )  y2 = (Sint32)m_sizeY;
			
			Flag orCollected = 0;
			for( int y = y1; y < y2; y++ ) {
				for( int x = x1; x < x2; x++ ) {
					orCollected |= m_flags.getValueAt( x, y );
				}
			}
			return orCollected;
		}

/******************************************************************************/

		bool testPassable( const Uint32 x, const Uint32 y, const Flag mask ) {
			return ! (m_flags.getValueAt( x, y ) & mask);
		}

/******************************************************************************/

		bool testPassableClip( const Uint32 x, const Uint32 y, const Flag mask ) {
			if( x >= m_sizeX || y >= m_sizeY ) return false;
			return ! (m_flags.getValueAt( x, y ) & mask);
		}

/******************************************************************************/

		bool testPassableSmoothing( const Uint32 x, const Uint32 y,
		                            const Flag mask ) {
			DBG( 5 ) {
				if( x >= m_sizeX || y >= m_sizeY ) {
					CHECK( false, "Map::testPassableSmoothing: coordinates out of bounds: "
					              "(%3i, %3i)\n", x, y );
					return false;
				}
			}

			const Flag& flag = m_flags.getReferenceTo( x, y );
			
			if( ! (flag & mask) ) {
				/*
				int passableNeighbors = 0;
				if( m_flags.getValueAt( x-1, y-1 ) & Flag::PASSABLE ) passableNeighbors++;
				if( m_flags.getValueAt( x  , y-1 ) & Flag::PASSABLE ) passableNeighbors++;
				if( m_flags.getValueAt( x+1, y-1 ) & Flag::PASSABLE ) passableNeighbors++;
				if( m_flags.getValueAt( x-1, y   ) & Flag::PASSABLE ) passableNeighbors++;
				if( m_flags.getValueAt( x+1, y   ) & Flag::PASSABLE ) passableNeighbors++;
				if( m_flags.getValueAt( x-1, y+1 ) & Flag::PASSABLE ) passableNeighbors++;
				if( m_flags.getValueAt( x  , y+1 ) & Flag::PASSABLE ) passableNeighbors++;
				if( m_flags.getValueAt( x+1, y+1 ) & Flag::PASSABLE ) passableNeighbors++;
				
				if( passableNeighbors <= 3 ) {
					LOG( 4 ) INFO( "Map::testPassableSmoothing: isolated hole => fill pixel\n" );
					m_flags.getReferenceTo( x, y ) &= ~Flag::PASSABLE;
					m_pixels.setValueAt( x, y, 0x00ff00 );
					return false;
				}*/
				return true;
			}
			else {
				if( ! (flag & Flags::UNSMOOTHABLE) ) {
					int passableNeighbors = 0;
					if( ! (m_flags.getValueAt( x-1, y-1 ) & mask) ) passableNeighbors++;
					if( ! (m_flags.getValueAt( x  , y-1 ) & mask) ) passableNeighbors++;
					if( ! (m_flags.getValueAt( x+1, y-1 ) & mask) ) passableNeighbors++;
					if( ! (m_flags.getValueAt( x-1, y   ) & mask) ) passableNeighbors++;
					if( ! (m_flags.getValueAt( x+1, y   ) & mask) ) passableNeighbors++;
					if( ! (m_flags.getValueAt( x-1, y+1 ) & mask) ) passableNeighbors++;
					if( ! (m_flags.getValueAt( x  , y+1 ) & mask) ) passableNeighbors++;
					if( ! (m_flags.getValueAt( x+1, y+1 ) & mask) ) passableNeighbors++;
					
					if( passableNeighbors >= 5 ) {
						LOG( 5 ) INFO( "Map::testPassableSmoothing: isolated pixel => destroy pixel\n" );
						destroyEarthPixel( x, y, 0 );
						DBG( 5 ) setColorAt( x, y, 0, 255, 0 );
						return true;
					}
				}
				return false;
			}
		}

/******************************************************************************/

		void makeRectHole( const Sint32 sx, const Sint32 sy, const Sint32 width,
		                   const Sint32 height, const Flag mask ) {
			for( int y = sy; y < sy + height; y++ )
				for( int x = sx; x < sx + width; x++ )
					destroyEarthPixelClip( x, y, mask );
		}

/******************************************************************************/

		void makeHole( const Sint32 xc, const Sint32 yc,
		               const Sint32 size, const Flag mask ) {
			Sint32 x = 0;
			Sint32 y = size;
			real d = 1.25 - static_cast<real>( size );
			
			Sint32 i;
			for ( i = -x; i <= x; i++ ) {
				destroyEarthPixelClip( xc + i, yc + y, mask );
				destroyEarthPixelClip( xc + i, yc - y, mask );
			}
			for ( i = -y; i <= y; i++ ) {
				destroyEarthPixelClip( xc + i, yc + x, mask );
				destroyEarthPixelClip( xc + i, yc - x, mask );
			}
			
			while ( y > x ) {
				x++;
				if ( d > 0 ) {
					y--;
					d += 2.0 * (x - y);
				}
				else {
					d += 2.0 * x + 1.0;
				}
				
				for ( i = -x; i <= x; i++ ) {
					destroyEarthPixelClip( xc + i, yc + y, mask );
					destroyEarthPixelClip( xc + i, yc - y, mask );
				}
				for ( i = -y; i <= y; i++ ) {
					destroyEarthPixelClip( xc + i, yc + x, mask );
					destroyEarthPixelClip( xc + i, yc - x, mask );
				}
			}
		}
		
/******************************************************************************/

		void setSpecialEarth( const Uint32 x, const Uint32 y,
		                      const Flag flag ) {
			// check clipping
			if( x >=  m_sizeX  || y >=  m_sizeY ) return;

			real brightness;
			int r, g, b;
			
			if( flag & Flags::INDESTRUCTIBLE ) {
				brightness = 0.5 + 0.2*localRnd.getNormedReal();
				r = g = b = static_cast<int>( 0x9c * brightness );
			}
			else if( flag & Flags::UNDIGGABLE ) {
				brightness = 0.5 + 0.2*localRnd.getNormedReal();
				r = static_cast<int>( 0x9c * brightness ),
				g = static_cast<int>( 0x5a * brightness ),
				b = static_cast<int>( 0x31 * brightness );
			} else {
				brightness = 0.7 + 0.3*localRnd.getNormedReal();
				r = static_cast<int>( 0x9c * brightness );
				g = static_cast<int>( 0x5a * brightness );
				b = static_cast<int>( 0x31 * brightness );
			}
			
			setColorAt( x, y, r, g, b );
			m_flags.getReferenceTo( x, y ) = flag;
		}
		
/******************************************************************************/

		void makeStone( const Sint32 xc, const Sint32 yc, const Sint32 size,
		                const Flag flag, const Flag mask ) {
			Sint32 x = 0;
			Sint32 y = size;
			real d = 1.25 - static_cast<real>( size );
			
			Sint32 i;
			for ( i = -x; i <= x; i++ ) {
				if( testPassableClip( xc + i, yc + y, mask )) setSpecialEarth( xc + i, yc + y, flag );
				if( testPassableClip( xc + i, yc - y, mask )) setSpecialEarth( xc + i, yc - y, flag );
			}
			for ( i = -y; i <= y; i++ ) {
				if( testPassableClip( xc + i, yc + x, mask )) setSpecialEarth( xc + i, yc + x, flag );
				if( testPassableClip( xc + i, yc - x, mask )) setSpecialEarth( xc + i, yc - x, flag );
			}
			
			while ( y > x ) {
				x++;
				if ( d > 0 ) {
					y--;
					d += 2.0 * (x - y);
				}
				else {
					d += 2.0 * x + 1.0;
				}
				
				for ( i = -x; i <= x; i++ ) {
					if( testPassableClip( xc + i, yc + y, mask )) setSpecialEarth( xc + i, yc + y, flag );
					if( testPassableClip( xc + i, yc - y, mask )) setSpecialEarth( xc + i, yc - y, flag );
				}
				for ( i = -y; i <= y; i++ ) {
					if( testPassableClip( xc + i, yc + x, mask )) setSpecialEarth( xc + i, yc + x, flag );
					if( testPassableClip( xc + i, yc - x, mask )) setSpecialEarth( xc + i, yc - x, flag );
				}
			}
		}
		
/******************************************************************************/

		real calculateBounceAngle( const real dx, const real dy,
		                            const int cx, const int cy, const Flag mask ) {
			static const int  dxTest[8] = { 0,  1,  1,  1,  0, -1, -1, -1},
			                  dyTest[8] = {-1, -1,  0,  1,  1,  1,  0, -1};
			const real incomingAngle = ATAN2_REAL( dy, dx );
			int incomingDir = static_cast<int>( 8*incomingAngle/(2*M_PI) + 6.5 ) % 8;
			
			if( ! testPassableSmoothing( cx + dxTest[incomingDir],
			                             cy + dyTest[incomingDir], mask ) ) {
				incomingDir = (incomingDir + 1) % 8;
				if( ! testPassableSmoothing( cx + dxTest[incomingDir],
				                             cy + dyTest[incomingDir], mask ) ) {
					incomingDir = (incomingDir + 6) % 8;
					if( ! testPassableSmoothing( cx + dxTest[incomingDir],
					                             cy + dyTest[incomingDir], mask ) ) {
						incomingDir = (incomingDir + 1) % 8;
					}
				}
			}
			
			int cwTest = (incomingDir+1) % 8, ccwTest = (incomingDir+7) % 8;
			
			LOG( 5 )
			INFO( "Map::calculateBounceAngle:\n%c%c%c\n%c%c%c\n%c%c%c\n",
			      (testPassableSmoothing( cx - 1, cy - 1, mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx    , cy - 1, mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx + 1, cy - 1, mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx - 1, cy    , mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx    , cy    , mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx + 1, cy    , mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx - 1, cy + 1, mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx    , cy + 1, mask ) ? '.' : '#'),
			      (testPassableSmoothing( cx + 1, cy + 1, mask ) ? '.' : '#') );
			
			// look for obstacles in clockwise direction
			while( testPassableSmoothing( cx + dxTest[cwTest], cy + dyTest[cwTest], mask )
			       && cwTest != incomingDir )
				cwTest = (cwTest+1) % 8;
			
			// look for obstacles in counter-clockwise direction
			while( testPassableSmoothing( cx + dxTest[ccwTest], cy + dyTest[ccwTest], mask )
			       && ccwTest != incomingDir )
				ccwTest = (ccwTest+7) % 8;
			
			LOG( 5 ) INFO( "incomingDir: %i; cwTest: %i; ccwTest: %i\n",
			      incomingDir, cwTest, ccwTest );
			
			/*
			if( (ccwTest-cwTest+8) % 8 <= 2 ) {
				return -incomingAngle;
			}
			else {
			*/
				return -incomingAngle + (M_PI*45.0/180.0)*(cwTest+ccwTest);
			//}
		}
		
/******************************************************************************/

		bool testCollRect( const int px, const int py,
		                   const int width, const int height,
		                   int& cx, int& cy ) {
			LOG( 5 ) INFO( "Map::testCollRect: px: %3i; py: %3i; width: %3i; height: %3i\n",
			                px, py, width, height );
			
			for( int x = px; x < px+width; x++ ) {
				//m_pixels.setValueAt( x, py, 0xffff00 );
				if( ! testPassableSmoothing( x, py, Flags::OBSTACLE_EARTH | Flags::OBSTACLE_OBJECT ) ) {
					cx = x; cy = py;
					LOG( 5 ) INFO( "Acoll at %i, %i\n", cx, cy );
					DBG( 5 ) setColorAt( cx, cy, 0, 255, 0 );
					return false;
				}
				//m_pixels.setValueAt( x, py+height-1, 0xffff00 );
				if( ! testPassableSmoothing( x, py+height-1, Flags::OBSTACLE_EARTH | Flags::OBSTACLE_OBJECT ) ) {
					cx = x; cy = py+height-1;
					LOG( 5 ) INFO( "Bcoll at %i, %i\n", cx, cy );
					DBG( 5 ) setColorAt( cx, cy, 0, 255, 0 );
					return false;
				}
			}
			
			for( int y = py+1; y < py+height-1; y++ ) {
				//m_pixels.setValueAt( px      , y, 0xffff00 );
				if( ! testPassableSmoothing( px, y, Flags::OBSTACLE_EARTH | Flags::OBSTACLE_OBJECT ) ) {
					cx = px; cy = y;
					LOG( 5 ) INFO( "Ccoll at %i, %i\n", cx, cy );
					DBG( 5 ) setColorAt( cx, cy, 0, 255, 0 );
					return false;
				}
				//m_pixels.setValueAt( px+width-1, y, 0xffff00 );
				if( ! testPassableSmoothing( px+width-1, y, Flags::OBSTACLE_EARTH | Flags::OBSTACLE_OBJECT ) ) {
					cx = px+width-1; cy = y;
					LOG( 5 ) INFO( "Dcoll at %i, %i\n", cx, cy );
					DBG( 5 ) setColorAt( cx, cy, 0, 255, 0 );
					return false;
				}
			}
			
			return true;
		}

/******************************************************************************/

		bool testFilledCollRect( const int px, const int py,
		                         const int width, const int height ) {
			LOG( 5 ) INFO( "Map::testFilledCollRect: px: %3i; py: %3i; width: %3i; height: %3i\n",
			                px, py, width, height );

			// check clipping
			if( px < 0 || py < 0 || static_cast<Uint32>( px+width  ) >=  m_sizeX  ||
			                        static_cast<Uint32>( py+height ) >=  m_sizeY ) {
				return false;
			}

			for( int y = py; y < py+height; y++ ) {
				for( int x = px; x < px+width; x++ ) {
					//m_pixels.setValueAt( x, py, 0xffff00 );
					if( ! testPassableSmoothing( x, y, Flags::OBSTACLE_EARTH | Flags::OBSTACLE_OBJECT ) ) {
						return false;
					}
				}
			}
			
			return true;
		}
		
/******************************************************************************/

		bool testFilledCollRectCollPos( const int px, const int py,
		                                const int width, const int height,
		                                int& cx, int& cy ) {
			LOG( 5 ) INFO( "Map::testFilledCollRect: px: %3i; py: %3i; width: %3i; height: %3i\n",
			                px, py, width, height );

			// check clipping
			if( px < 0 || py < 0 || static_cast<Uint32>( px+width  ) >=  m_sizeX  ||
			                        static_cast<Uint32>( py+height ) >=  m_sizeY ) {
				cx = cy = -1;
				return false;
			}

			for( cy = py; cy < py+height; cy++ ) {
				for( cx = px; cx < px+width; cx++ ) {
					//m_pixels.setValueAt( x, py, 0xffff00 );
					if( ! testPassableSmoothing( cx, cy, Flags::OBSTACLE_EARTH | Flags::OBSTACLE_OBJECT ) ) {
						return false;
					}
				}
			}
			
			return true;
		}
		
/******************************************************************************/

		void setCollRect( const int px, const int py,
		                  const int width, const int height ) {
			LOG( 5 ) INFO( "Map::setCollRect: setting collision rectangle at (%i, %i, %i, %i)\n",
			               px, py, width, height );
			bool saveFlagsLater = false;
			String comment;
			DBG( 3 ) {
				if( ! CHECK( testFilledCollRect( px, py, width, height ),
				             "Map::setCollRect: collRect not completely passable\n" ) ) {
					comment.format( "Map::setCollRect: collRect( %i, %i, %i, %i ) not "
					                "completely passable", px, py,
					                width, height );
					saveFlagsLater = true;
				}
			}

			int x, y;
			for( y = py; y < py+height; y++ ) {
				for( x = px; x < px+width; x++ ) {
					m_flags.getReferenceTo( x, y ) |= Flags::OBSTACLE_OBJECT | Flags::UNABLE_ANY;
				}
			}
			
			if( saveFlagsLater ) saveFlags( comment );
		}
		
/******************************************************************************/

		void removeCollRect( const int px, const int py,
		                     const int width, const int height ) {
			int x, y;
			for( y = py; y < py+height; y++ ) {
				for( x = px; x < px+width; x++ ) {
					m_flags.getReferenceTo( x, y ) &= ~(Flags::OBSTACLE_OBJECT | Flags::UNABLE_ANY);
				}
			}
		}
		
/******************************************************************************/

		bool testLineCollRect( int x1, int y1, int x2, int y2,
		                       const int width, const int height,
		                       int& pcx, int& pcy, int& cx, int& cy ) {
			int i;
			int sx, sy;  // step positive or negative (1 or -1)
			int dx, dy;  // delta (difference in X and Y between points)
			int e;
			
			LOG( 5 ) INFO( "Map::testLineCollRect: x1: %3i; y1: %3i; x2: %3i; y2: %3i; width: %3i; height: %3i\n",
			               x1, y1, x2, y2, width, height );
			dx = abs( x2 - x1 );
			sx = (x2 - x1 > 0) ? 1 : -1;
			dy = abs( y2 - y1 );
			sy = (y2 - y1 > 0) ? 1 : -1;
			
			cx = pcx = x1; cy = pcy = y1;
			
			if( dy <= dx ) {
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					if( ! testCollRect( x1, y1, width, height, cx, cy ) ) {
						DBG( 3 ) CHECK( ! (pcx == cx && pcy == cy && &pcx != &cx), "Map::testLineCollRect: "
						                "precollision coords == collision coords (A) "
						                "(%i, %i) -> (%i, %i) preColl: (%i, %i), coll: "
						                "(%i, %i)\n", x1, y1, x2, y2, pcx, pcy, cx, cy );
						return false;
					}
					else { pcx = x1; pcy = y1; }
					
					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
			else {
		#define SWAP(a,b) {int tmpswap = a; a = b; b = tmpswap;}
				SWAP(x1, y1); SWAP(dx, dy); SWAP(sx, sy);
		#undef SWAP
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					if( ! testCollRect( y1, x1, width, height, cx, cy ) ) {
						DBG( 3 ) CHECK( ! (pcx == cx && pcy == cy && &pcx != &cx), "Map::testLineCollRect: "
						                "precollision coords == collision coords (B) "
						                "(%i, %i) -> (%i, %i) preColl: (%i, %i), coll: "
						                "(%i, %i)\n", y1, x1, x2, y2, pcx, pcy, cx, cy );
						return false;
					}
					else { pcx = y1; pcy = x1; }
					
					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
			
			return true;
		}

/******************************************************************************/

		bool testLinePassable( int x1, int y1, int x2, int y2,
		                       int& pcx, int& pcy, int& cx, int& cy,
		                       const Flag mask ) {
			int i;
			int sx, sy;  // step positive or negative (1 or -1)
			int dx, dy;  // delta (difference in X and Y between points)
			int e;
			
			dx = abs( x2 - x1 );
			sx = (x2 - x1 > 0) ? 1 : -1;
			dy = abs( y2 - y1 );
			sy = (y2 - y1 > 0) ? 1 : -1;
			
			cx = pcx = x1; cy = pcy = y1;
			
			if( dy <= dx ) {
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					if( ! testPassable( x1, y1, mask ) ) {
						cx = x1; cy = y1;
						DBG( 5 ) CHECK( ! (pcx == cx && pcy == cy && &pcx != &cx), "Map::testLinePassable: "
						                "precollision coords == collision coords (A) "
						                "(%i, %i) -> (%i, %i) preColl: (%i, %i), coll: "
						                "(%i, %i)\n", x1, y1, x2, y2, pcx, pcy, cx, cy );
						return false;
					}
					else { pcx = x1; pcy = y1; }
					
					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
			else {
		#define SWAP(a,b) {int tmpswap = a; a = b; b = tmpswap;}
				SWAP(x1, y1); SWAP(dx, dy); SWAP(sx, sy);
		#undef SWAP
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					if( ! testPassable( y1, x1, mask ) ) {
						cx = y1; cy = x1;
						DBG( 5 ) CHECK( ! (pcx == cx && pcy == cy && &pcx != &cx), "Map::testLinePassable: "
						                "precollision coords == collision coords (B) "
						                "(%i, %i) -> (%i, %i) preColl: (%i, %i), coll: "
						                "(%i, %i)\n", y1, x1, x2, y2, pcx, pcy, cx, cy );
						return false;
					}
					else { pcx = y1; pcy = x1; }
					
					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
			
			return true;
		}

/******************************************************************************/

		bool testLinePassableSmoothing( int x1, int y1, int x2, int y2,
		                                int& pcx, int& pcy, int& cx, int& cy,
		                                const Flag mask ) {
			int i;
			int sx, sy;  // step positive or negative (1 or -1)
			int dx, dy;  // delta (difference in X and Y between points)
			int e;
			
			dx = abs( x2 - x1 );
			sx = (x2 - x1 > 0) ? 1 : -1;
			dy = abs( y2 - y1 );
			sy = (y2 - y1 > 0) ? 1 : -1;
			
			cx = pcx = x1; cy = pcy = y1;
			
			if( dy <= dx ) {
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					if( ! testPassableSmoothing( x1, y1, mask ) ) {
						cx = x1; cy = y1;
						DBG( 5 ) CHECK( ! (pcx == cx && pcy == cy && &pcx != &cx), "Map::testLinePassableSmoothing: "
						                "precollision coords == collision coords (A) "
						                "(%i, %i) -> (%i, %i) preColl: (%i, %i), coll: "
						                "(%i, %i)\n", x1, y1, x2, y2, pcx, pcy, cx, cy );
						return false;
					}
					else { pcx = x1; pcy = y1; }
					
					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
			else {
		#define SWAP(a,b) {int tmpswap = a; a = b; b = tmpswap;}
				SWAP(x1, y1); SWAP(dx, dy); SWAP(sx, sy);
		#undef SWAP
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					if( ! testPassableSmoothing( y1, x1, mask ) ) {
						cx = y1; cy = x1;
						DBG( 5 ) CHECK( ! (pcx == cx && pcy == cy && &pcx != &cx), "Map::testLinePassableSmoothing: "
						                "precollision coords == collision coords (B) "
						                "(%i, %i) -> (%i, %i) preColl: (%i, %i), coll: "
						                "(%i, %i)\n", y1, x1, x2, y2, pcx, pcy, cx, cy );
						return false;
					}
					else { pcx = y1; pcy = x1; }
					
					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
			
			return true;
		}

/******************************************************************************/

		void drawLine( int x1, int y1, int x2, int y2, const Uint32 col) {
			int i;
			int sx, sy;  // step positive or negative (1 or -1)
			int dx, dy;  // delta (difference in X and Y between points)
			int e;
			
			dx = abs( x2 - x1 );
			sx = (x2 - x1 > 0) ? 1 : -1;
			dy = abs( y2 - y1 );
			sy = (y2 - y1 > 0) ? 1 : -1;
			
			if( dy <= dx ) {
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					setColorAt( x1, y1, col );
					
					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
			else {
		#define SWAP(a,b) {int tmpswap = a; a = b; b = tmpswap;}
				SWAP(x1, y1); SWAP(dx, dy); SWAP(sx, sy);
		#undef SWAP
				e = (dy << 1) - dx;
				for( i = 0; i <= dx; i++ ) {
					setColorAt( y1, x1, col );

					if( e >= 0 ) {
						y1 += sy; e -= (dx << 1);
					}
					x1 += sx; e += (dy << 1);
				}
			}
		}
		
};

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

class ServerMap : public Map, public Serializable {
	private:
		//! Storage for the foreground pixels
		MapMemory<Uint32> m_pixels;
		//! Default format for the map on the server 
		SDL_PixelFormat m_pixelFormat;
		
	public:
		//! Constructor
		ServerMap( int sizeX, int sizeY )
			: Map( sizeX, sizeY ),
			  m_pixels( sizeX, sizeY ) {
			m_pixelFormat.palette = 0;
			m_pixelFormat.BitsPerPixel = 32;
			m_pixelFormat.BytesPerPixel = 4;
			m_pixelFormat.Rmask = 0x000000ff;
			m_pixelFormat.Gmask = 0x0000ff00;
			m_pixelFormat.Bmask = 0x00ff0000;
			m_pixelFormat.Amask = 0x00000000;
			m_pixelFormat.Rshift = 0;
			m_pixelFormat.Gshift = 8;
			m_pixelFormat.Bshift = 16;
			m_pixelFormat.Ashift = 24;
			m_pixelFormat.Rloss = 0;
			m_pixelFormat.Gloss = 0;
			m_pixelFormat.Bloss = 0;
			m_pixelFormat.Aloss = 0;
		}
		
/******************************************************************************/

		// Destructor
		virtual ~ServerMap() {
			LOG( 4 ) INFO( "ServerMap::~ServerMap: destructor called\n" );
		}
		
/******************************************************************************/

		// returns a pointer to the pixel container
		MapMemory<Uint32>* getPixels() {
			return &m_pixels;
		}
		
/******************************************************************************/

		const SDL_PixelFormat* getPixelFormat() const {
			return &m_pixelFormat;
		}
		
/******************************************************************************/

		virtual void getColorAt( const Uint32 x, const Uint32 y,
		                         Uint8& red, Uint8& green, Uint8& blue ) {
			Uint32 pixel = m_pixels.getValueAt( x, y );
			SDL_GetRGB( pixel, &m_pixelFormat, &red, &green, &blue );
		}
		
/******************************************************************************/

		virtual void setColorAt( const Uint32 x, const Uint32 y,
		                         const Uint8 r, const Uint8 g, const Uint8 b ) {
			const Uint32 pixel = SDL_MapRGB( &m_pixelFormat, r, g, b );
			m_pixels.setValueAt( x, y, pixel );
		}
		
/******************************************************************************/

		virtual void setColorAt( const Uint32 x, const Uint32 y, const Uint32 color ) {
			const Uint8 r = static_cast<Uint8>( color >> 16 ),
			            g = static_cast<Uint8>( color >>  8 ),
			            b = static_cast<Uint8>( color       );
			const Uint32 pixel = SDL_MapRGB( &m_pixelFormat, r, g, b );
			m_pixels.setValueAt( x, y, pixel );
		}
		
/******************************************************************************/

		//! creates a map from a theme
//		void createFromTheme( Theme& theme, World& world );
		//! fills the map with random circles
//		void fillWithRandomCircles();
		//! places the passed sprite as map stuff of passed material
		void placeMapStuffItem( const Sprite* const item,
		                        const Sprite* const flags,
		                        const Uint32 x, const Uint32 y,
		                        const int material,
		                        const bool smoothable = true );	
		//! places the passed sprite as map stuff of passed material
		void placeMapStuffItem( const Sprite* const item,
		                        const Uint32 x, const Uint32 y,
		                        const int material,
		                        const bool smoothable = true ) {
			placeMapStuffItem( item, item, x, y, material, smoothable );
		}
		
		//! \name (de)serialization
		//@{
		//! return the size of the serialized map
		virtual Uint32 getSerializeBufferSize() const {
			return 2 * Serialize<Uint32>::sizeOf() +
				m_pixels.getSerializeBufferSize() +
				m_flags.getSerializeBufferSize();
		}
		
		/*! \brief serialize the map into the buffer starting at
		 *  bufferPointer. After this method bufferPointer points to
		 *  next char after the last char of the serialization of the
		 *  map.
		 */
		virtual void serialize( Uint8*& bufferPointer ) const;

		/*! \brief create a new map out of a serialization in the buffer
		 *  starting at bufferPointer. After this method bufferPointer
		 *  points to next char after the last char of the serialization
		 *  of the map.
		 */
		static ServerMap* createAndDeserialize( Uint8*& bufferPointer );

		/*! \brief replace the existing map by deserializing the contents
		 *  of the buffer pointed to by bufferPointer. After this method
		 *  bufferPointer points to next char after the last char of the
		 *  serialization of the map.
		 */
		virtual void deserialize( Uint8*& bufferPointer );
		//@}
};

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

class ClientMap : public Map {
	private:
		//! Storage for the foreground pixels
		SDL_Surface* m_pixels;
		
/******************************************************************************/

	public:
		//! Constructor
		ClientMap( ServerMap& serverMap, SDL_PixelFormat* format, Uint32 flags )
			: Map( *serverMap.getFlags() ) {
			LOG( 3 ) INFO( "ClientMap::ClientMap: Constructor called\n" );
			LOG( 4 ) INFO( "ClientMap::ClientMap: Create surface from server map data\n" );
			SDL_Surface* serverSurface =
				SDL_CreateRGBSurfaceFrom( serverMap.getPixels()->getMemory(),
				                          serverMap.getSizeX(), serverMap.getSizeY(),
				                          serverMap.getPixelFormat()->BitsPerPixel,
				                          serverMap.getPixelFormat()->BytesPerPixel *
				                          serverMap.getSizeX(),
				                          serverMap.getPixelFormat()->Rmask,
				                          serverMap.getPixelFormat()->Gmask,
				                          serverMap.getPixelFormat()->Bmask,
				                          serverMap.getPixelFormat()->Amask );
			ASSERT( serverSurface, "ClientMap::ClientMap: could not create surface\n" );
			LOG( 4 ) INFO( "ClientMap::ClientMap: Converting server surface to client format\n" );
			m_pixels = SDL_ConvertSurface( serverSurface, format, flags );
			ASSERT( m_pixels, "ClientMap::ClientMap: could not convert surface\n" );
			LOG( 4 ) INFO( "ClientMap::ClientMap: Freeing server surface\n" );
			SDL_FreeSurface( serverSurface );
		}
		
/******************************************************************************/

		//! Copy constructor
		ClientMap( const ClientMap& m ) : Map( m ) {
			m_pixels = SDL_CreateRGBSurface
				( m.m_pixels->flags, m.m_pixels->w, m.m_pixels->h,
				  m.m_pixels->format->BitsPerPixel,
				  m.m_pixels->format->Rmask,
				  m.m_pixels->format->Gmask,
				  m.m_pixels->format->Bmask,
				  m.m_pixels->format->Amask );
			ASSERT( m_pixels, "ClientMap::ClientMap: could not create surface\n" );
			SDL_BlitSurface( m.m_pixels, 0, m_pixels, 0 );
		}
		
/******************************************************************************/

		// Destructor
		virtual ~ClientMap() {
			LOG( 3 ) INFO( "ClientMap::~ClientMap: destructor called\n" );
			SDL_FreeSurface( m_pixels );
		}
		
		SDL_Surface* getPixels() {
			return m_pixels;
		}
		
/******************************************************************************/

		virtual void getColorAt( const Uint32 x, const Uint32 y,
		                         Uint8& red, Uint8& green, Uint8& blue ) {
			Uint32 pixel = Graphics::getPixel( m_pixels, x, y );
			SDL_GetRGB( pixel, m_pixels->format, &red, &green, &blue );
		}
		
/******************************************************************************/

		virtual void setColorAt( const Uint32 x, const Uint32 y,
		                         const Uint8 r, const Uint8 g, const Uint8 b ) {
			const Uint32 pixel = SDL_MapRGB( m_pixels->format, r, g, b );
			Graphics::setPixel( m_pixels, x, y, pixel );
		}
		
/******************************************************************************/

		virtual void setColorAt( const Uint32 x, const Uint32 y, const Uint32 color ) {
			const Uint8 r = static_cast<Uint8>( color >> 16 ),
			            g = static_cast<Uint8>( color >>  8 ),
			            b = static_cast<Uint8>( color       );
			const Uint32 pixel = SDL_MapRGB( m_pixels->format, r, g, b );
			Graphics::setPixel( m_pixels, x, y, pixel );
		}
		
/******************************************************************************/

		//! \name (de)serialization
		//@{
		//! return the size of the serialized map
		virtual Uint32 getSerializeBufferSize() const {
			return 2 * Serialize<Uint32>::sizeOf() +
				m_pixels->h * m_pixels->pitch +
				m_flags.getSerializeBufferSize();
		}
		
		/*! \brief serialize the map into the buffer starting at
		 *  bufferPointer. After this method bufferPointer points to
		 *  next char after the last char of the serialization of the
		 *  map.
		 */
		virtual void serialize( Uint8*& bufferPointer ) const;
		
		/*! \brief replace the existing map by deserializing the contents
		 *  of the buffer pointed to by bufferPointer. After this method
		 *  bufferPointer points to next char after the last char of the
		 *  serialization of the map.
		 */
		virtual void deserialize( Uint8*& bufferPointer );
		//@}
};

#endif // _MAP_HPP_