Khatharr

This code is just in response to what you asked me about. There's still problems here that other people have touched on. Additionally, your render code seems too close to your logic. You should try to separate these into different sections unless the program structure is exceedingly simplistic.

const int MOVE_DIST = 42;
const int BOUNDARY_MIN = 0;
const int BOUNDARY_MAX = 378;

//Handle movement (see other people's comments about testing against SDLK_ constants)
if(SDLK_UP)    {PlayerLocationy -= MOVE_DIST;}
if(SDLK_DOWN)  {PlayerLocationy += MOVE_DIST;}
if(SDLK_LEFT)  {PlayerLocationx -= MOVE_DIST;}
if(SDLK_RIGHT) {PlayerLocationx += MOVE_DIST;}

//Correct out-of-bounds condition
Message = NULL;
if(PlayerLocationy < BOUNDARY_MIN) {
  Message = DeniedMessage;
  PlayerLocationy = BOUNDARY_MIN;
}
if(PlayerLocationy > BOUNDARY_MAX) {
  Message = DeniedMessage;
  PlayerLocationy = BOUNDARY_MAX;
}
if(PlayerLocationx < BOUNDARY_MIN) {
  Message = DeniedMessage;
  PlayerLocationx = BOUNDARY_MIN;
}
if(PlayerLocationy > BOUNDARY_MAX) {
  Message = DeniedMessage;
  PlayerLocationx = BOUNDARY_MAX;
}

//Render
if(Message != NULL) {
  int mess_x = (ScreenWidth - Message->w) / 2;
  //This next line is not clear. Get rid of the magic number and clarify order of operations
  int mess_y = (ScreenHeight - Message->h + 420) / 2;

  ApplySurface(mess_x,mess_y,Message,Screen,NULL);

  Message = NULL;
}
else {
  ApplySurface(0,421,Sprites,Screen,&TextBox);
}

 
The key here is that the things you're likely to change are easy to change and it's clear what's going on. You can change the constants at the top or the render stuff at the bottom and not have to worry about changing it all 4 times. The organization and alignment of the first set of tests also makes it easier to spot if there's any errors lurking there, such as having PlayerLocationy where there should be a PlayerLocationx, or a - where there should be a +.

Which distance model are you using and what is AL_ROLLOFF_FACTOR set to?

I think you're going to save yourself a lot of time, now and in the future, if you immediately remove all the repetition here. As it is, any change you make to the core routine here has to be made 4 times, and that means 4 times the probability that you'll make another mistake.
 
DRY

I think this is generally handled by storing the tilemap as an array or 2D (or 3D) array of id numbers, then storing the tile images in a single texture in order of their id numbers. This allows the tilemap to be rendered efficiently from a single texture. You just iterate through each tile in the map and render that block from the texture into place. If you need to store passability data or other metadata you can just use a second array of packed data, such as a byte array where each byte is a bitmask indicating passability directions.

Have a separate distro for each platform?