Imagine a grid that covers the entire map. Each cell in this grid can only hold one unit at a time. When a unit moves from one cell to another, it marks the cell it's going to as "occupied" so that other units can't take it. When a unit leaves a cell, it marks it as "free".
There are two types of obstacles: temporary (like another unit occupying a cell) and permanent (like a river that the unit will have to go around).
Every time a unit moves to an adjacent cell, it checks if it's occupied by another unit. If the cell is occupied, the unit tries to find a way to go around it.