Sachverhalt:
A.
Im Frühjahr 2008 orientierte die Gemeinde Bühler die Bevölkerung über ihr Vorhaben, die Gebäude- und Strassenadressierung zu erneuern. Am 5. Dezember 2009 nahm der Gemeinderat von Bühler von einer unter dem Titel "Adressen Revision Bühler" lancierten Petition Kenntnis. Am 16. Dezember 2009 beschloss der Gemeinderat die neuen Strassennamen und Hausnummern (Adressenplan 1) und bestimmte, dass sie ab 1. Juni 2010 gelten würden. Nach einem Gespräch mit den Petitionären veröffentlichte der Gemeinderat seinen Beschluss am 12. Januar 2010. Am 20. Januar 2010 verlangten die "Erstunterzeichner Adressrevision Bühler" mittels "offenem Brief" vom Gemeinderat den sofortigen Stopp aller angekündigten Schritte und die Wiedererwägung der Petition unter Einbezug der Bevölkerung.
Im März und im April 2010 versandte die Gemeinde Bühler Informationsschreiben an die Bevölkerung mit den neuen, ab 1. Juni 2010 gültigen Adressen.
Am 3. April 2010 rekurrierten A._ und D._ ans Departement Bau und Umwelt des Kantons Appenzell Ausserrhoden, wobei sie u.a. beantragten, den Rekursen aufschiebende Wirkung zuzuerkennen und die nach ihrer Auffassung Verfügungen darstellenden Adressänderungen und den Strassenplan aufzuheben. Am 25. April 2010 erhob E._ wegen der neuen Gebäudeadressierung Aufsichtsbeschwerde gegen den Gemeinderat Bühler. Am 19. Mai 2010 reichten mehrere Einwohner weitere Rekurse ein.
Am 7. Oktober 2010 hiess das Departement die Rekurse, soweit es darauf eintrat, gut (Dispositiv-Ziffer 1) und wies die Sache im Sinne der Erwägungen an die Gemeinde zurück (Dispositiv-Ziffer 2). Es erwog, die behördliche Anordnung der Neuadressierung sei für die Privaten mit intensivem Aufwand verbunden und habe für diese unmittelbare Rechtswirkungen. Die Schreiben der Gemeinde vom März und April 2010 seien damit anfechtbare Verfügungen. Die Adressrevision erscheine für das Gemeindegebiet von Bühler als nicht sachgerecht und die Neuzuteilung der Adressen als unangemessen. Das Departement wies die Gemeinde an, in Bezug auf die Neuzuteilung der Adressen eine sachgerechte Lösung zu realisieren und empfahl ihr, sich durch Fachpersonen beraten zu lassen und mit den Rekurrenten bzw. Petitionären das Gespräch zu suchen und allenfalls eine zweite Volksdiskussion durchzuführen. Es erhob keine Staatsgebühr (Dispositiv-Ziffer 3) und verpflichtete die Gemeinde Bühler, den Rekurrenten eine Parteientschädigung von insgesamt Fr. 1'000.-- zu bezahlen (Dispositiv-Ziffer 4).
Die Gemeinde Bühler focht diesen Departementsentscheid beim Obergericht des Kantons Appenzell Ausserrhoden an mit den Anträgen, ihn aufzuheben und auf die Rekurse nicht einzutreten oder sie eventuell abzuweisen. A._ (Beschwerdegegner 1), D._ (Beschwerdegegnerin 2), E._ (Beschwerdegegner 3) sowie eine von Rechtsanwalt Gassmann vertretene Gruppe von weiteren Rekurrenten (Beschwerdegegner 4) widersetzten sich der Beschwerde.
Im Oktober 2010 setzte der Gemeinderat Bühler eine Arbeitsgruppe unter der Leitung von Oberrichter Nänny ein mit dem Auftrag, den umstrittenen Adressenplan zu überarbeiten. Am 6. Juni 2011 präsentierte die Arbeitsgruppe ein Teilresultat. Dieser Adressenplan 2 wurde in der Folge öffentlich aufgelegt.
Am 30. Juni 2011 beantragte die Gemeinde Bühler, das Verwaltungsgerichtsverfahren zu sistieren. Die Beschwerdegegner widersetzten sich dem Antrag.
Am 22. November 2012 gab der Gemeinderat Bühler bekannt, dass er die Adressen gemäss Vorschlag der Arbeitsgruppe Nänny am 1. Januar 2013 in Kraft setzen werde.
Am 3. August 2011 wurde das Verfahren auf Antrag der Gemeinde Bühler sistiert. Am 17. September 2012 beantragte diese, die Sistierung aufzuheben.
Am 23. November 2012 beantragten die Beschwerdegegner, das Verfahren ohne weitere Diskussion abzuschreiben. Am 15. Januar 2013 beantragte die Gemeinde Bühler, das Verfahren als gegenstandslos geworden abzuschreiben.
Am 11. Februar 2013 schrieb der Obergerichtspräsident das Verfahren infolge Gegenstandslosigkeit ab (Dispositiv-Ziffer 1). Er hob den Entscheid des Departements vom 7. Oktober 2010 bezüglich der den damaligen Rekurrenten zugesprochenen Parteientschädigung auf und befreite die Gemeinde Bühler von der Bezahlung einer Parteientschädigung in Höhe von Fr. 1'000.-- (Dispositiv-Ziffer 2). Die Kosten des Verwaltungsgerichtsverfahrens in Höhe von Fr. 1'200.-- auferlegte er den Beschwerdegegnern 1 - 4 je zu gleichen Teilen (Dispositiv-Ziffer 3). Er stellte fest, das keine Partei der anderen eine Parteientschädigung schulde (Dispositiv-Ziffer 4).
B.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen A._ sowie B.X._ und C.X._, es sei die Nichtigkeit von Dispositiv-Ziffer 2 des angefochtenen Entscheids festzustellen, oder sie sei eventuell aufzuheben. Dispositiv-Ziffer 3 sei aufzuheben. Dispositiv-Ziffer 4 sei aufzuheben und den Beschwerdeführern für das Verwaltungsgerichtsverfahren eine Parteientschädigung zuzusprechen. Ausserdem ersuchen sie, ihrer Beschwerde in Bezug auf Dispositiv-Ziffer 3 aufschiebende Wirkung zuzuerkennen.
C.
Am 17. April 2013 erkannte der Präsident der I. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zu.
D.
Das Departement Bau und Umwelt teilt in seiner Vernehmlassung die Ansicht der Beschwerdeführer, dass der angefochtene Entscheid insofern widersprüchlich sei, indem er das Verfahren einerseits infolge Gegenstandslosigkeit abschreibe, aber anderseits dennoch den Entscheid des Departements vom 7. Oktober 2010 teilweise aufhebe. Im Übrigen verzichtete des Departement auf Vernehmlassung.
Die Gemeinde Bühler beantragt, auf die Beschwerde nicht einzutreten, soweit sie von C.X._ geführt werde, und sie abzuweisen, soweit sie von A._ und B.X._ erhoben worden sei. Das Obergericht beantragt, die Beschwerde abzuweisen.
Die Beschwerdeführer halten in ihrer Replik an der Beschwerde fest.

Erwägungen:
1.
Beim angefochtenen Entscheid des Obergerichtspräsidenten handelt es sich um einen kantonal letztinstanzlichen Entscheid in einer Angelegenheit des öffentlichen Rechts (Art. 82 lit. a, Art. 86 Abs. 1 lit. d BGG). Es liegt keine Ausnahme im Sinn von <ref-law> vor. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist zulässig, womit für die subsidiäre Verfassungsbeschwerde kein Raum bleibt. Die Beschwerdeführer haben am kantonalen Verfahren als Parteien teilgenommen; sie sind durch die Auferlegung von Kosten vom angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>). Ob sich B.X._ am kantonalen Verfahren gemeinsam mit seiner Ehefrau C.X._ beteiligte und letztere irrtümlicherweise im Rubrum des angefochtenen Entscheids nicht aufgeführt wurde, oder, wie die Beschwerdegegnerin geltend macht, als Einzelperson mit der Folge, dass C.X._ nicht beschwerdebefugt wäre, kann offen bleiben. Es spielt für den Ausgang des Verfahrens keine Rolle, ob B.X._ allein oder gemeinsam mit seiner Ehefrau Beschwerde führt. Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, weshalb auf die Beschwerde einzutreten ist. Soweit im Folgenden auf Vorbringen der Beschwerdeführer und Gegenbemerkungen der Beschwerdegegnerin nicht eingegangen wird, sind sie für den Ausgang des Verfahrens unerheblich.
2.
2.1. Die Beschwerdegegnerin (und damalige Beschwerdeführerin) hat sich dem Departementsentscheid vom 7. Oktober 2010 einerseits unterzogen, indem sie nach dessen Anweisung die Überarbeitung des Adressenplans 1 einleitete. Anderseits hielt sie sich für den Fall eines Scheiterns der Überarbeitung des Adressenplans 1 den Rechtsweg offen, indem sie gegen den Departementsentscheid Verwaltungsgerichtsbeschwerde erhob. Dieses zweigleisige Vorgehen ist, entgegen der Auffassung der Beschwerdeführer, durchaus legitim und keineswegs widersprüchlich.
2.2. Die Beschwerdegegnerin (und damalige Beschwerdeführerin) hatte auf dem politischen Weg Erfolg und konnte auf den 1. Januar 2013 den Adressenplan 2 nach dem Vorschlag der Arbeitsgruppe Nänny in Kraft setzen. Unbestritten ist, dass das Verwaltungsgerichtsbeschwerdeverfahren damit gegenstandslos wurde und dementsprechend vom Obergerichtspräsidenten zu Recht abgeschrieben wurde. Damit hatte er neben den Kosten- und Entschädigungsfolgen des verwaltungsgerichtlichen Verfahrens auch diejenigen des Verwaltungsverfahrens zu regeln oder regeln zu lassen. Da der Departementsentscheid nie in Rechtskraft erwuchs, war die Aufhebung von dessen Dispositiv-Ziffer 4 betreffend der Zusprechung einer Parteientschädigung an die damaligen Rekurrenten durch den Obergerichtspräsidenten allerdings falsch und überflüssig. Dispositiv-Ziffer 2 des angefochtenen Entscheids des Obergerichtspräsidenten ist dementsprechend aufzuheben, ohne dass dies an der Rechtslage etwas ändern würde.
2.3. Nach den unbestrittenen Ausführungen des Obergerichtspräsidenten im angefochtenen Entscheid regelt das einschlägige kantonale Verfahrensrecht die Kosten- und Entschädigungsfolgen für den Fall, dass das Verfahren gegenstandslos wird, nicht explizit. Er ist daher davon ausgegangen, dass die Verfahrenkosten bei Gegenstandslosigkeit die Partei zu tragen hat, die deren Eintritt verursacht hat. Ist sie ohne Zutun der Parteien eingetreten, sind die Kosten nach der Sachlage vor dem Eintreten zu verlegen (angefochtener Entscheid E. 3 Absatz 2 S. 12). Dies entspricht im Wesentlichen der Praxis des Bundesgerichts, wonach die Kosten, wenn keine der Parteien die Gegenstandslosigkeit verursacht hat, nach dem mutmasslichen Ausgang des Verfahrens zu verlegen sind; die Prüfung der Prozessaussichten soll dabei keine weiteren Umstände verursachen und keine heiklen Rechtsfragen präjudizieren. Auf dem Weg über den Kostenentscheid soll kein materielles Urteil gefällt werden, weshalb es bei einer summarischen Beurteilung der Aktenlage sein Bewenden haben muss (<ref-ruling> E. 2a; Urteil 2C_237/2009 vom 28. September 2009 E. 3.1). Da es vorliegend um die Anwendung von kantonalem Verfahrensrecht geht, prüft das Bundesgericht die hier umstrittene Kosten- und Entschädigungsregelung nur auf Willkür.
2.3.1. Wie die Beschwerdeführer zu Recht vorbringen, hat sich die Beschwerdegegnerin dem Entscheid des Departements klarerweise unterzogen und einen abgeänderten, von keiner Seite angefochtenen Adressenplan 2 erlassen. Mit dessen In-Kraft-Treten war der Streitgegenstand des verwaltungsgerichtlichen Verfahrens bildende Adressenplan 1 überholt und das Verfahren gegenstandslos. Der Obergerichtspräsident hält dazu zwar fest, der Adressenplan 2 beruhe auf einer geänderten gesetzlichen Grundlage und berücksichtige nicht alle Anliegen der Beschwerdeführer, weshalb nicht davon gesprochen werden könne, die Gemeinde habe sich dem Entscheid des Departements unterzogen.
Das überzeugt nicht. Art. 34 der am 1. November 2012 in Kraft getretenen kantonalen Verordnung über die amtliche Vermessung, auf den der Obergerichtspräsident in diesem Zusammenhang verweist, legt lediglich fest, dass die zuständige Gemeindebehörde - hier der Gemeinderat - neue oder geänderte Strassennamen beschliesst. Diese Kompetenz hat indessen der Gemeinderat mit dem Beschluss vom 16. Dezember 2009 schon vorher für sich in Anspruch genommen. Vor allem aber ist weder dargetan noch ersichtlich, inwiefern die Änderung der Rechtsgrundlagen die Überarbeitung des Adressenplans 1 beeinflusst haben könnte. Das Departement hat von der Gemeinde auch keineswegs verlangt, einseitig alle Standpunkte der Beschwerdeführer (und damaligen Rekurrenten) zu übernehmen, sondern nur, deren berechtigten Anliegen Rechnung zu tragen und den als teilweise unsachgemäss beurteilten Adressen- bzw. Strassenplan zu überarbeiten. Das tat die Gemeinde offenbar mit Erfolg, blieb doch der Adressenplan 2 unangefochten.
2.3.2. Der Obergerichtspräsident hat im angefochtenen Entscheid erwogen, dass die Verwaltungsgerichtsbeschwerde der Gemeinde mutmasslich hätte gutgeheissen werden müssen. Das Departement hätte auf die Verwaltungsbeschwerde nicht eintreten dürfen, weil die angefochtenen Schreiben der Gemeinde mit der Mitteilung der neuen Adressen keine anfechtbaren Verfügungen, sondern nicht anfechtbare Realakte darstellten. Diese Rechtsauffassung, die sich auf Tobias Jaag (Zur Rechtsnatur der Strassenbezeichnung, in: Recht 1993, S. 53 ff.) stützen kann, hat Einiges für sich. Dementsprechend ist die Einschätzung des Obergerichtspräsidenten, die Beschwerdegegnerin hätte im Verfahren mit überwiegender Wahrscheinlichkeit obsiegt, bei summarischer Prüfung jedenfalls vertretbar. Das ist allerdings für die Beurteilung der Kosten- und Entschädigungsfolgen unerheblich, da sich die Beschwerdegegnerin dem Departementsentscheid unterzogen (oben E. 2.3.1) und dadurch die Gegenstandslosigkeit verursacht hat.
2.3.3. Für das Verwaltungsverfahren vor dem Departement hat der Obergerichtspräsident keine Kosten erhoben und keine Parteientschädigungen zugesprochen. Der Beschwerdeführer 1 war als Partei und als Parteienvertreter am Verfahren beteiligt. Das Bundesgericht spricht in bei ihm hängigen Verfahren nicht anwaltlich vertretenen Parteien und sich selber vertretenden Anwälten nur ausnahmsweise - etwa bei einem ausserordentlich hohen Aufwand - Parteientschädigungen zu (<ref-ruling> E. 4.1; <ref-ruling> E. 5; <ref-ruling> nicht publ. E. 6; <ref-ruling> E. 4d; Urteile 1B_596/2012 vom 14. März 2013 E. 3 und 1B_158/2012 vom 15. Oktober 2012 E. 3). Da weder dargetan noch ersichtlich ist, dass im Verwaltungsverfahren ein besonderer, das übliche Mass sprengender Aufwand erforderlich war, ist es jedenfalls unter Willkürgesichtspunkten im Ergebnis nicht zu beanstanden, dass die Beschwerdeführer (bzw. die damaligen Rekurrenten) keine Parteientschädigung zugesprochen erhalten. Die Beschwerde ist insoweit unbegründet.
2.3.4. Für das verwaltungsgerichtliche Verfahren hätten den Beschwerdeführern (bzw. damaligen Beschwerdegegnern) nach dem Gesagten klarerweise keine Kosten auferlegt werden dürfen; die Kostenauflage in Dispositiv-Ziffer 3 des angefochtenen Entscheids ist somit als willkürlich aufzuheben. Was die Zusprechung einer Parteientschädigung betrifft, gilt grundsätzlich das Gleiche wie für das erstinstanzliche Verfahren: deren Verweigerung ist im Ergebnis haltbar und die Beschwerde insoweit unbegründet.
3.
Die Beschwerde ist somit teilweise gutzuheissen und die Dispositiv-Ziffern 2 und 3 des angefochtenen Entscheids aufzuheben; im Übrigen ist sie abzuweisen. Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (<ref-law>). In Bezug auf eine allfällige Parteientschädigung fällt nach der in E. 2.3.3 angeführten Praxis in Betracht, dass die Beschwerdeführer im kantonalen Verfahren nicht entschädigt wurden und gesamthaft betrachtet, über drei Instanzen und einen langen Zeitraum von rund vier Jahren hinweg einen insgesamt hohen Aufwand treiben mussten. Es rechtfertigt sich daher, ihnen ausnahmsweise eine angemessene Parteientschädigung zuzusprechen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen und die Dispositiv-Ziffern 2 und 3 des obergerichtlichen Entscheids vom 11. Februar 2013 aufgehoben; im Übrigen wird sie abgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Die Beschwerdegegnerin hat den Beschwerdeführern 1 und 2 eine Parteientschädigung von je Fr. 750.--, insgesamt Fr. 1'500.--, zu bezahlen.
4.
Dieses Urteil wird den Parteien, dem Departement Bau und Umwelt Appenzell Ausserrhoden und dem Obergericht Appenzell Ausserrhoden, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 19. Dezember 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Störi