The tile grid doesn't necessarily need to be an integral part of it, as Servant indicated; you can superimpose a movement grid upon the generated map, marking tiles as passable or impassable based upon the average terrain they encompass.

That was Kryzon actually. It's a very important realization used by more modern games. Freely placing, blending, rotating, scaling images, and then have collision rects and pathfinding nodes over those. I've considered it for my own games, but decided to mix both together: Tile based, but then also allowing freely-placed sprites over the tiles.

Whoops, yeah, sorry about that Kryzon. :D