Cell migration is a complex process involving many intracellular and extracellular factors, with different cell types adopting sometimes strikingly different morphologies. Modeling realistically behaving cells in tissues is computationally challenging because it implies dealing with multiple levels of complexity. We extend the Cellular Potts Model with an actin-inspired feedback mechanism that allows small stochastic cell rufflings to expand to cell protrusions. This simple phenomenological model produces realistically crawling and deforming amoeboid cells, and gliding half-moon shaped keratocyte-like cells. Both cell types can migrate randomly or follow directional cues. They can squeeze in between other cells in densely populated environments or migrate collectively. The model is computationally light, which allows the study of large, dense and heterogeneous tissues containing cells with realistic shapes and migratory properties.