La optimización, viene luego  
Te dejo un enlace para que pruebes:

Sin colisiones
Con colisiones

Pues haz algo que vaya leyendo 1 a 1 del array y lo vaya guardando 1 a 1 en el vector unidimensional
Guarda cuantos valores tiene el array por coordenada y desde ahí, es fácil

jajajaja que bueno Saurik xD 

Muchas gracias 
Lo de la velocidad nueva, no lo había pensado jajaja

Escrotofagia 

Sé la velocidad con la que se mueve hacia la cara (constante)
Sé la cara con la que choca
Sé la dirección del personaje

Menisco

Si, es lo que estoy intentando: que cuando choques con una cara, la dirección hacia esa cara se bloquee y no se desplace hacia ese eje. He conseguido hacerlo bastante decente, ya os contaré 

Popeye

Saco una foto, estoy haciendo un game engine (mi primer juego, justo acababa de aprender c++ de forma decente cuando me metí con OpenGL). Os cuento el problema desde el principio:
Tengo 3 tipos de detectores de colisiones programados:
 - Bounding sphere (para cosas que no requieren precision absoluta como coger monedas)
 - Axis aligned Bounding Box (Los bloques de terreno "B")
 - Objet aligned bounding box (El personaje "A")
Tengo programada una simulación de la gravedad que hace que cada frame (el juego está capado a 30fps) baje un poco a no ser que haya colision. Detectar la colision entre los dos bloques es fácil, pero no sé luego como saber si estoy chocando de frente, de costado... y a partir de eso evitar ciertos movimientos como caminar hacia el objeto (deslizarse por el objeto)
Dejo un video del juego en cuestión (Minuto 2:15, donde el cursor es rojo, es el que digo)