Angiogenesis, the formation of new blood vessels sprouting from existing ones, occurs in several situations like wound healing, tissue remodeling, and near growing tumors. Under hypoxic conditions, tumor cells secrete growth factors, including VEGF. VEGF activates endothelial cells (ECs) in nearby vessels, leading to the migration of ECs out of the vessel and the formation of growing sprouts. A key process in angiogenesis is cellular self-organization, and previous modeling studies have identified mechanisms for producing networks and sprouts. Most theoretical studies of cellular self-organization during angiogenesis have ignored the interactions of ECs with the extra-cellular matrix (ECM), the jelly or hard materials that cells live in. Apart from providing structural support to cells, the ECM may play a key role in the coordination of cellular motility during angiogenesis. For example, by modifying the ECM, ECs can affect the motility of other ECs, long after they have left. Here, we present an explorative study of the cellular self-organization resulting from such ECM-coordinated cell migration. We show that a set of biologically-motivated, cell behavioral rules, including chemotaxis, haptotaxis, haptokinesis, and ECM-guided proliferation suffice for forming sprouts and branching vascular trees.