What is the pattern of horizontal and vertical lines that cross each other at right angles called on a map?

a grid or coordinate system

on maps of earth the coordinate system is longitude and latitude. Any point on earth can be located using longitude and latitude. Other maps use longitude/latitude and height above or below a known location (mean sea level) to locate a point in 3 dimensions.

Star maps use grid systems and degree systems similar to longitude and latitude to help locate objects relative to earth.

Many smaller tourist maps and map books will have a arbitrary grid system imposed to ease the finding of places using an index ex lookup main street - the index says it on page 20, J 4.